# Solutions for Problem 3

Find the largest prime factor of a composite number.

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

What is the largest prime factor of the number 600851475143 ?

## Python by Althalus

Runtime: 1.5 seconds

```from math import sqrt
import time

start_time = time.time()

#We want to find the largest prime factor of this number.
number=600851475143
#No point starting at 1, dont need to include 1 or the original number in our list of factors
i=3

#List of factors.
factors=[]

#Will be our answer when we've finished.
biggest_factor=0

#By the time we reach the square root of number, we've got all factors.
while i <= sqrt(number):
if i%5 != 0: #number ends in 3 :. not multiple of 5.
if number%i == 0:
factors.append(i)
factors.append(int(number/i))

i+=2#number is odd, :. no even factors.

factors.sort(reverse=True) #Biggest number first.

#Go thru all the factors, looking for a prime.
for factor in factors:
factor_factors=[]
i=3
while i <= sqrt(factor):
if i%5 !=0:
if factor%i==0:
factor_factors.append(i)
factor_factors.append(int(factor/i))
i+=2
#Found it.
if len(factor_factors) == 0:
biggest_factor = factor
break

print (biggest_factor)
run_time = time.time() - start_time
print (run_time)
```

## python by astan (traltixx)

Runtime: 119.423000 seconds

```   import time, math
start_time = time.time()
limit = 600851475143
max = 1
for i in range(2,int(math.sqrt(limit))+1):
prime = True
for p in range(2,int(math.sqrt(i))+1):
if i%p == 0:
prime = False
if limit%i == 0 and max < i and prime:
max = i
print max
run_time = time.time() - start_time
print 'Run time: %f seconds' % run_time
```

Runtime: 3.350 seconds

```{- Same old primes generator as in problems 7 and 10. -}
primes :: [Integer]
primes = 2:3:primes'
where
1:p:candidates  = [6*k+r | k <- [0..], r <- [1,5]]
primes'        = p : filter isPrime candidates
isPrime n       = all (not . divides n) \$ takeWhile (\p -> p*p <= n) primes'
divides n p     = n `mod` p == 0

{- Some explanation of how this works:
- "head" takes the first element of the list
- "filter" returns only the elements that are factors of 600851475143
- "reverse" the primes to make finding the largest one MUCH faster
- "takeWhile" for primes less than 775146, the square root of 600851475143
- Same old list of primes as before.
-}
(filter (\x -> 600851475143 `mod` x == 0)
(reverse (takeWhile (< 775146) primes))))
```

## C++ by ctd

Runtime: 21ms

```#include <cmath>
#include <list>
#include <iostream>
#define TARGET 600851475143ULL
using namespace std;

bool isPrime (long long);

int main ()
{
list<long long> factors;
long long i, largest = 0, upper = sqrt(TARGET);
for (i = 1; i <= upper; i++) {
if (TARGET % i == 0) {
factors.push_back(i);
}
}
list<long long>::iterator itr;
for (itr = factors.end(); largest == 0 && itr != factors.begin(); itr--)
if (isPrime(*itr))
largest = *itr;

cout << largest << endl;

return 0;
}

bool isPrime (long long i)
{
if (i <= 1) return false;
long long upper = sqrt (i) + 1;
for (long long lower = 2; lower < upper; lower++) {
if (i % lower == 0)
return false;
}
return true;
}
```