Максимальное количество делителей в диапазоне

@WillyamAnsuok · Регистрация: 08.05.2019

Author24 — интернет-сервис помощи студентам

Здравствуйте, нужна помощь по оптимизации программы.
Вот сама программа

Python

a = int(input())
b = int(input())
c = []
d = []
for i in range(a, b + 1):
    count = 0
    for j in range(1, i // 2 + 1):
        if i % j == 0:
            count += 1
    c.append(count)
for i in range(a, b + 1):
    d.append(i)
e = max(c)
f = c.index(e, 0, len(c))
print(d[f])

ЧИсла а и б таковы: В первой строке входных данных записано число a, во второй строке записано число b
(1 ⩽ a ⩽ b ⩽ 10⁶, b − a ⩽ 3000).
ПРи этом ограничение по времени 2 секунды
При крупных числах очень долго производит операции и не укладывается во время.

@Viktorrus · 08.05.2019, 20:51

WillyamAnsuok, Таких тем было уже несколько, и однозначно можно сказать, что при больших числах напрямую перебором поиск делителей происходит очень долго, выполняется часами. Может существуют какие то математические алгоритмы для быстрого поиска делителей, я не знаю.
Если на практике, а не для тестирующей программы понадобиться искать делители, то я знаю только один, быстро работающий способ. Создать таблицу простых чисел, заранее их найдя, и потом использовать эту таблицу для поиска делителей. Но это не для тестирующей программы.
Кстати в Википедии есть таблица с 500 первыми простыми числами.

Python

Первые 500 простых чисел из википедии:
nums = [ 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,
179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,
419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,
547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,
661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,
811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,
947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,
1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,
1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,
1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,
1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,
1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,
1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,
1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,
2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,
2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,
2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,
2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,
2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,
2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,
3083,3089,3109,3119,3121,3137,3163,3167,3169,3181,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,
3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,
3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,3517,3527,3529,3533,3539,3541,3547,3557,3559,3571 ]

@WillyamAnsuok · 08.05.2019, 21:02 **[ТС]**

Viktorrus, Спасибо, я уже пока сидел вывел и для больших чисел формулу.
Нужно смотреть от а до корня из б, и потом, если корень из б иррациональный, то просто умножаем на 2 кол-во получившихся делителей, если же корень целый, то умножаем на два и вычитаем 1

@Viktorrus · 08.05.2019, 21:27

WillyamAnsuok, Когда напишете код, используя Ваш алгоритм, если не сложно, выложите его сюда. Так как такие задачи периодически появляются на форуме.

@WillyamAnsuok · 08.05.2019, 21:50 **[ТС]**

Viktorrus,

Python

a = int(input())
b = int(input())
c = []
d = []
for i in range(a, b + 1):
    count = 0
    for j in range(1, int(i ** 0.5) + 1):
        if i % j == 0:
            count += 1
    if float(i ** 0.5) != int(i ** 0.5):
        c.append( 2 * count)
    else:
        c.append( 2 * count - 1)
for i in range(a, b + 1):
    d.append(i)
e = max(c)
f = c.index(e)
print(d[f])

Добавлено через 10 минут
Алгоритм рабочий, но долгий. Сейчас занимаюсь оптимизацией

@Viktorrus · 09.05.2019, 04:41

WillyamAnsuok, Я оказывается перепутал количество делителей и разложение на простые числа. Буду разбираться.

Добавлено через 1 час 9 минут
Вот написал правильный код использующий таблицу.

Python

    # Первые 500 простых чисел из википедии:
nums = [ 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,
179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,
419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,
547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,
661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,
811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,
947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,
1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,
1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,
1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,
1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,
1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,
1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,
1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,
2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,
2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,
2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,
2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,
2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,
2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,
3083,3089,3109,3119,3121,3137,3163,3167,3169,3181,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,
3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,
3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,3517,3527,3529,3533,3539,3541,3547,3557,3559,3571 ]
 
def numberDiv(N):
    #count = 2
    if N in nums:
        return 2
    x = N
    L = []
    for p in nums:
        if x < p:
            break
        countP = 0
        while x % p == 0:
            countP += 1
            x = x / p
        L.append(countP)
        if x in nums:
            L.append(1)
            #count += 1
            break
    count = 1
    for i in L:
        count *= i + 1
    return count
 
if __name__ == '__main__':
    A = int(input('Введите A не больше 3500: '))
    B = int(input('Введите B не больше 3500: '))
    maxDiv = 0
    maxDivN = 0
    for i in range(A, B + 1):
        n = numberDiv(i)
        print(i, ' => ', n)
        if n >= maxDiv:
            maxDiv = n
            maxDivN = i
    print('максимум делителей у ', maxDivN)

Пример:

Python

Введите A не больше 3500: 500
Введите B не больше 3500: 3500
500  =>  12
501  =>  4
502  =>  4
503  =>  2
504  =>  24
505  =>  4
...........................
2517  =>  4
2518  =>  4
2519  =>  4
2520  =>  48
2521  =>  2
2522  =>  8
2523  =>  6
...........................
3358  =>  8
3359  =>  2
3360  =>  48
3361  =>  2
3362  =>  6
............................
3497  =>  4
3498  =>  16
3499  =>  2
3500  =>  24
максимум делителей у  3360

Подтверждает правильность Вашего алгоритма, хотя и работает медленнее чем у Вас.
Ваш код выдает число 2520. Оно имеет 48 делителей.
У меня выдает число 3360 , которое имеет тоже 48 делителей.
У этих двух чисел максимальное количество делителей в диапазоне от 500 до 3500.

@WillyamAnsuok 0 / 0 / 0 Регистрация: 08.05.2019 Сообщений: 3
	08.05.2019, 21:02 [ТС]	3
	Viktorrus, Спасибо, я уже пока сидел вывел и для больших чисел формулу. Нужно смотреть от а до корня из б, и потом, если корень из б иррациональный, то просто умножаем на 2 кол-во получившихся делителей, если же корень целый, то умножаем на два и вычитаем 1 0

@Viktorrus 1728 / 968 / 199 Регистрация: 22.02.2018 Сообщений: 2,694 Записей в блоге: 6
	08.05.2019, 21:27	4
	WillyamAnsuok, Когда напишете код, используя Ваш алгоритм, если не сложно, выложите его сюда. Так как такие задачи периодически появляются на форуме. 0

	09.05.2019, 04:41