The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

In [2]:

primes = range(120)

In [4]:

primes = [i for i in primes if i%2 != 0]

In [5]:

def num_list(num):
    primes = [i for i in range(num)]
    for i in primes:
        yield i

In [6]:

[i for i in num_list(10)]

Out[6]:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

In [7]:

[i for i in num_list(10) if i%i != 0]

---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
<ipython-input-7-354e48873b71> in <module>()
----> 1 [i for i in num_list(10) if i%i != 0]

ZeroDivisionError: integer division or modulo by zero

In [8]:

primes = range(2, 10)

while primes:
    x = primes.pop(0)
    print x, primes
    primes = [i for i in primes if i%x != 0]

2 [3, 4, 5, 6, 7, 8, 9]
3 [5, 7, 9]
5 [7]
7 []

In [9]:

def prime_list(num):
    primes = range(2, num)

    while primes:
        x = primes.pop(0)
        yield x
        primes = [i for i in primes if i%x != 0]

In [11]:

[ i for i in prime_list(10)]

Out[11]:

[2, 3, 5, 7]

In [13]:

%%time
max([i for i in prime_list(100000) if 600851475143%i == 0])

CPU times: user 6.34 s, sys: 7.58 ms, total: 6.35 s
Wall time: 6.35 s

Out[13]:

In [14]:

600851475143/6857

Out[14]:

87625999

In [15]:

%%time
max([i for i in prime_list(100000) if 87625999%i == 0])

CPU times: user 6.45 s, sys: 18.6 ms, total: 6.47 s
Wall time: 6.46 s

Out[15]:

In [17]:

87625999/1471

Out[17]:

In [18]:

%%time
max([i for i in prime_list(100000) if 59569%i == 0])

CPU times: user 5.84 s, sys: 36.8 ms, total: 5.88 s
Wall time: 5.84 s

Out[18]:

In [35]:

plist = [i for i in prime_list(6856)]

In [36]:

poss = [i for i in plist if 600851475143%i == 0]
print poss

[71, 839, 1471]

In [37]:

for j in poss:
    maybe_prime = (600851475143/j)
    print j, maybe_prime, [i for i in plist if maybe_prime%i == 0]

71 8462696833 [839, 1471]
839 716151937 [71, 1471]
1471 408464633 [71, 839]

In [38]:

poss = [i for i in plist if 408464633%i == 0]
print poss

for j in poss:
    maybe_prime = (408464633/j)
    print j, maybe_prime, [i for i in plist if maybe_prime%i == 0]

[71, 839]
71 5753023 [839]
839 486847 [71]

In [49]:

def max_prime(num, guess):    
    primes = prime_list(guess)
    factors = [i for i in primes if num%i == 0]
    
    
    if num/reduce(lambda x, y: x*y, factors) < guess:
        return max(factors)
    else:
        raise ValueError("Guess too small")

In [50]:

max_prime(600851475143, 100000)

Out[50]:

In [ ]: