Runs quicker than i was expecting. For a large prime like "600851475143987", it completes it's run in under 10 seconds on my ancient core 2 duo work machine.
Since the number is prime, the list of prime factors is just itself.
[600851475143987L]
9.84399986267 seconds...
An unoptimized version that doesn't employ that bit of array arithmetic (2*index+1=possible prime factor) takes about 15 seconds, so it looks quirky, but these optimizations count!
unoptimized prime factor was:
def lowestprimefactor_bysieve(number):
sieve=[0]*int(round(1+pow(number,0.5)))
init=2
k=2
sieve[k]=2
while (k < len(sieve)):
if (sieve[k]!=1):
sieve[k]=2 #number is prime
if ((number%k==0)):
return int(k)
for idx in xrange(k,len(sieve),k):
sieve[idx]=1 #mark as a being a factor
if k>2:
k+=2
else:
k+=1
return int(number)
Here's the full code:
import sys
import time
def lowestprimefactor_bysieve(number):
sieve=[0]*int(round(1+pow(number,0.5)/2))
init=2
if (number%2==0):
return 2
k=1
sieve[k]=2
while (k < len(sieve)):
if (sieve[k]!=1):
realvalue=k*2+1
sieve[k]=2 #number is prime
if ((number%realvalue==0)):
return int(realvalue)
for idx in xrange(k,len(sieve),realvalue):
sieve[idx]=1 #mark as a being a factor
k+=1
return int(number)
def primefactorlist_sieve(number):
lfac=lowestprimefactor_bysieve(number)
if lfac==number:
return [lfac]
return [lfac]+primefactorlist_sieve(number//lfac)
def main():
#What is the largest prime factor of the number 600851475143 ?
number=600851475143
start = time.time()
print(primefactorlist_sieve(number))
print(time.time() - start)
if __name__ == '__main__':
main()
