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

@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.

Новые блоги и статьи
Обновление сайта www.historian.by Reglage 13.01.2025 За неделю добавил два урока - по ассемблеру и Линуксу, а также дополнил один урок по ассемблеру. Мелкими шагами двигаюсь дальше к неизменной цели. По ИТ: 1) добавил урок "Структура программы на. . .	Введение в модели и алгоритмы машинного обучения InfoMaster 12.01.2025 Машинное обучение представляет собой одну из наиболее динамично развивающихся областей искусственного интеллекта, которая фокусируется на разработке алгоритмов и методов, позволяющих компьютерам. . .	Как на Python создать нейросеть для решения задач InfoMaster 12.01.2025 В контексте стремительного развития современных технологий особое внимание уделяется таким инструментам, как нейросети. Эти структуры, вдохновленные биологическими нейронными сетями, используются для. . .	Как создать нейросеть для генерации картинок на Python InfoMaster 12.01.2025 Генерация изображений с помощью искусственных нейронных сетей стала одним из наиболее захватывающих направлений в области компьютерного зрения и машинного обучения. В этой статье мы рассмотрим. . .	Создание нейросети для генерации текста на Python InfoMaster 12.01.2025 Нейросети, или искусственные нейронные сети, представляют собой модели машинного обучения, вдохновленные работой человеческого мозга. Они состоят из множества взаимосвязанных узлов, или "нейронов",. . .	Как создать нейросеть распознавания изображений на Python InfoMaster 12.01.2025 Введение в распознавание изображений с помощью нейросетей Распознавание изображений с помощью нейронных сетей стало одним из самых впечатляющих достижений в области искусственного интеллекта. Эта. . .
Основы искуственного интеллекта InfoMaster 12.01.2025 Искусственный интеллект (ИИ) представляет собой одну из наиболее динамично развивающихся областей современной науки и технологий. В широком смысле под искусственным интеллектом понимается способность. . .	Python и нейросети InfoMaster 12.01.2025 Искусственные нейронные сети стали неотъемлемой частью современных технологий, революционизировав множество областей - от медицинской диагностики до автономных транспортных средств. Python, благодаря. . .	Python в машинном обучении InfoMaster 12.01.2025 Python стал неотъемлемой частью современного машинного обучения, завоевав позицию ведущего языка программирования в этой области. Его популярность обусловлена несколькими ключевыми факторами, которые. . .	Создание UI на Python с TKinter InfoMaster 12.01.2025 TKinter — это одна из наиболее популярных библиотек для создания графических интерфейсов пользователей (GUI) в языке программирования Python. TKinter входит в стандартную библиотеку Python, что. . .	HTML5 в разработке мобильных приложений InfoMaster 12.01.2025 Введение: Обзор роли HTML5 в мобильной разработке В современном мире мобильных технологий HTML5 стал ключевым инструментом для разработки кроссплатформенных приложений. Эта технология произвела. . .	Как создавать приложения для iOS/iPhone InfoMaster 12.01.2025 Введение в разработку iOS-приложений Разработка приложений для iOS открывает огромные возможности в мире мобильных технологий. С каждым годом количество пользователей iPhone и iPad растет,. . .

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

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

	09.05.2019, 04:41