Простой алгоритм, перебирающий все возможные делители $d$, начиная с $2$, пока $d^2\le a$. Четные пробные делители (кроме $2$) пропускаются.
def factor(a):
'''
Разложение числа на простые множители.
Функция находит все простые делители заданного числа.
Вход:
a - заданное число, a ≥ 2
Выход:
список всех простых делителей числа n;
каждый делитель повторяется столько раз,
какова его кратность; делители расположены
в порядке возрастания
'''
divisors = []
while a % 2 == 0:
divisors.append(2)
a //= 2
d = 3
while d*d <= a:
while (a % d) == 0:
divisors.append(d)
a //= d
d += 2
if a > 1:
divisors.append(a)
return divisors
for a in xrange(1, 101):
print a, factor(a)
1 [] 2 [2] 3 [3] 4 [2, 2] 5 [5] 6 [2, 3] 7 [7] 8 [2, 2, 2] 9 [3, 3] 10 [2, 5] 11 [11] 12 [2, 2, 3] 13 [13] 14 [2, 7] 15 [3, 5] 16 [2, 2, 2, 2] 17 [17] 18 [2, 3, 3] 19 [19] 20 [2, 2, 5] 21 [3, 7] 22 [2, 11] 23 [23] 24 [2, 2, 2, 3] 25 [5, 5] 26 [2, 13] 27 [3, 3, 3] 28 [2, 2, 7] 29 [29] 30 [2, 3, 5] 31 [31] 32 [2, 2, 2, 2, 2] 33 [3, 11] 34 [2, 17] 35 [5, 7] 36 [2, 2, 3, 3] 37 [37] 38 [2, 19] 39 [3, 13] 40 [2, 2, 2, 5] 41 [41] 42 [2, 3, 7] 43 [43] 44 [2, 2, 11] 45 [3, 3, 5] 46 [2, 23] 47 [47] 48 [2, 2, 2, 2, 3] 49 [7, 7] 50 [2, 5, 5] 51 [3, 17] 52 [2, 2, 13] 53 [53] 54 [2, 3, 3, 3] 55 [5, 11] 56 [2, 2, 2, 7] 57 [3, 19] 58 [2, 29] 59 [59] 60 [2, 2, 3, 5] 61 [61] 62 [2, 31] 63 [3, 3, 7] 64 [2, 2, 2, 2, 2, 2] 65 [5, 13] 66 [2, 3, 11] 67 [67] 68 [2, 2, 17] 69 [3, 23] 70 [2, 5, 7] 71 [71] 72 [2, 2, 2, 3, 3] 73 [73] 74 [2, 37] 75 [3, 5, 5] 76 [2, 2, 19] 77 [7, 11] 78 [2, 3, 13] 79 [79] 80 [2, 2, 2, 2, 5] 81 [3, 3, 3, 3] 82 [2, 41] 83 [83] 84 [2, 2, 3, 7] 85 [5, 17] 86 [2, 43] 87 [3, 29] 88 [2, 2, 2, 11] 89 [89] 90 [2, 3, 3, 5] 91 [7, 13] 92 [2, 2, 23] 93 [3, 31] 94 [2, 47] 95 [5, 19] 96 [2, 2, 2, 2, 2, 3] 97 [97] 98 [2, 7, 7] 99 [3, 3, 11] 100 [2, 2, 5, 5]
%time factor(11111111111111111)
Wall time: 515 ms
[2071723, 5363222357L]
%time factor(1111111111111111111)
Wall time: 4min 16s
[1111111111111111111L]
В качестве пробных делителей рассматриваются числа $2$, $3$ и числа вида $d = 6k \pm 1$, где $k\in{\bf N}$
def factor(a):
'''
Разложение числа на простые множители.
Функция находит все простые делители заданного числа.
Вход:
a - заданное число, a ≥ 2
Выход:
список всех простых делителей числа n;
каждый делитель повторяется столько раз,
какова его кратность; делители расположены
в порядке возрастания
'''
divisors = []
while a % 2 == 0:
divisors.append(2)
a //= 2
while a % 3 == 0:
divisors.append(3)
a //= 3
k = 1
while True:
d = 6*k - 1 # пробный делитель
if d*d > a:
break
while a % d == 0:
divisors.append(d)
a //= d
d = 6*k + 1 # пробный делитель
if d*d > a:
break
while a % d == 0:
divisors.append(d)
a //= d
k += 1
if a > 1:
divisors.append(a)
return divisors
for a in range(2, 21):
print a, factor(a)
2 [2] 3 [3] 4 [2, 2] 5 [5] 6 [2, 3] 7 [7] 8 [2, 2, 2] 9 [3, 3] 10 [2, 5] 11 [11] 12 [2, 2, 3] 13 [13] 14 [2, 7] 15 [3, 5] 16 [2, 2, 2, 2] 17 [17] 18 [2, 3, 3] 19 [19] 20 [2, 2, 5]
%time factor(11111111111111111)
Wall time: 397 ms
[2071723, 5363222357L]
%time factor(1111111111111111111)
Wall time: 3min 22s
[1111111111111111111L]