Euler 3 continued:

Here's the code for Euler 3 in Python (written in 2.7)

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()