Ускорение программы
Как можно ускорить программу для нахождение делителей? Нужно найти делители очень больших чисел.
a = int(input())
b = 0
for i in range(1,a+1):
if b > 10000:
break
elif a % i == 0:
b +=1
print(i)
print(b)
Ответы (3 шт):
Тема факторизации больших чисел много раз обсуждалась.
Если быть кратким, то:
Перестать проверять делимость четных чисел и на четные делители - там и так всё ясно.
Воспользоваться эффективными алгоритмами
Питон - это интерпретируемый язык, и есть сомнения в том, что в задачах, связанных со скоростью и эффективностью вычислений, его имеет смысл применять.
Ускорение в 2 раза:
for i in range(1,a//2+1):
Дальнейшее ускоренние: примени алгоритм поиска простых чисел.
- Решето Эратосфена
- Решето Сундарама
- Решето Аткина
А потом перебирай комбинации по 2 из простых чисел и рекурсивно для получившигося цисла комбинация с простым делителем.
Можно перебирать делители до корня из числа, при этом будет находиться два делителя один из которых до его корня, а другой после корня. За исключениям случая, когда число будет целым квадратом - тогда нужно будет еще его добавить.
import math
a = int(input())
b = 0
temp = math.isqrt(a)
if a == temp*temp:
b+=1
print(temp)
for i in range(1,temp):
if b > 10000:
break
elif a % i == 0:
b +=2
print(i)
print int(a/i)
print(b)
Порядок вывода делителей естественно будет не исходным.