Euler-sol-3

From ProgSoc Wiki

Jump to: navigation, search

Contents

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

Haskell by SanguineV

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.
 -}
main = print (head 
    (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;
}
Personal tools