A jakie są zakresy danych wejściowych? Bo na podanym przykładzie to dużo szybciej byłoby przelecieć sitem zakres sqrt(n)
a potem przelecieć po liczbach pierwszych w zakresie (z tablicy z sita) i znaleźć największą która dzieli n
. To wszystko przy założeniu że da się zmieścić w pamieci tablicę na sito.
Mój naiwny kod w pythonie od razu (w sensie momentalnie) daje odpowiedź że faktoryzacja tej liczby to [71, 839, 1471, 6857]
Więc zrobiłem coś takiego (kody z naszego https://github.com/p4-team/crypto-commons ;) ):
def get_primes(limit=1000000):
"""
Use sieve to get list of prime numbers in range
:param limit: range for search
:return: list of primes in range
"""
import math
m = limit + 1
numbers = [True for _ in range(m)]
for i in range(2, int(math.sqrt(limit))):
if numbers[i]:
for j in range(i * i, m, i):
numbers[j] = False
primes = []
for i in range(2, m):
if numbers[i]:
primes.append(i)
return primes
def factor(n, limit=1000000):
"""
Factor given value using sieve up to a certain limit
:param n: number to factor
:param limit: sieve limit
:return: list of factors and residue
"""
factors = []
primes = get_primes(limit)
for prime in primes:
while n % prime == 0 and n > 1:
n /= prime
factors.append(prime)
if n < 2:
break
return factors, n
I na podstawie tych 2 funkcji możemy sobie policzyć:
n = 600851475143
factors = factor(n, int(math.sqrt(n)))
print(factors)
Co daje ([71, 839, 1471, 6857], 1L)