# Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

This is the first problem I found with an interesting real world application.  Factoring primes is hard but multiplying out two primes is trivial.  That concept, called a one-way function, underpins modern cryptography.  The generation of large primes is a hard problem, but it is much harder to figure out which two primes were multiplied to make a given number than it is to generate those primes in the first place.  That's because modern computers are very, very good at multiplication and addition, but relatively slow at division.  Likewise, the brute force guessing of prime factors is very time consuming because there are a large number of primes.

All cryptography can be broken given enough time.  The trick is to make the math problem hard enough that the attacker gives up and does something else before he can decrypt your secrets.

# Solution

Here's the code for Problem 3:

`#!/usr/bin/pythondef isprime(val): #Checks to see if a number is prime, brute force    for x in range(2, int(val**0.5)+1):        if val % x == 0: return False    return Truedef factor(val):  #Get the prime factors of a number    if isprime(val): return [val]    i = 2    thesefactors = []    tempval = val    while (i &lt;= tempval):        if tempval%i == 0:            thesefactors += [i]            tempval = tempval/i            i = 2        else:            i = i + 1    if len(thesefactors) &lt;= 1:        return [val]    else:        return thesefactorsif __name__ == '__main__':    import sys    factors = factor(int(sys.argv))    print (factors)`

This is run using the following command (with the correct number argument for the question asked):

`python primes.py 600851475143`

The correct answer is 6857.

# Approach

Again, this is a brute force approach.  I have included a refinement called Newton's Improvement where you don't need to check if numbers larger than the square root of that number are factors.  This helps improve both subroutines.  These subroutines were both used in the solutions of later problems.

`for x in range(2, int(val**0.5)+1):`

# Benchmarks

The question asked was too easy to make a good benchmark, so I created my own composite using the solution of a later problem involving counting primes.  The two primes I multiplied were 1299379 and 1299709.  The multiplication takes the blink of an eye, but the factoring takes many, many blinks.

As before, pypy is about 7-10x faster than Python2, with Jython being much slower and Python3 somewhere in the middle.

`Problem #3 Benchmarkstime python primes.py 1688814580711[1299379, 1299709]real 0m0.329suser 0m0.316ssys 0m0.012stime python -O primes.py 1688814580711[1299379, 1299709]real 0m0.380suser 0m0.372ssys 0m0.004stime python3 primes.py 1688814580711[1299379, 1299709]real 0m0.715suser 0m0.704ssys 0m0.008stime python3 -O primes.py 1688814580711[1299379, 1299709]real 0m0.772suser 0m0.764ssys 0m0.004stime pypy primes.py 1688814580711[1299379, 1299709]real 0m0.083suser 0m0.080ssys 0m0.000stime pypy -O primes.py 1688814580711[1299379, 1299709]real 0m0.083suser 0m0.076ssys 0m0.004s`

# Conclusion

The Problem 3 solution is a program with both real world uses and utility as a library for later problems.  The problem of locating and factoring primes is the holy grail of cryptography and this simple implementation gives some insight into prime numbers and the problem of factoring primes.