Project Euler: Problem 3

Problem 3 on Project Euler is stated thus:

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

What is the largest prime factor of the number 600851475143 ?

Let us first try an easier problem, finding the largest prime factor of 51. The square root of 51 is between 7 and 8 so prepare a list of prime numbers up to 8:

2 3 5 7

Starting with the 2 we find that 3 is a factor of 51 (51 = 3 x 17). Starting with the 3 we then look for a factor for 17 in our list. We do not find one so we can assume that 17 is a prime number and the largest prime factor of 51.

Let us try this approach with another number, 1001. We start with a list of prime number up to the sqare root of n (which is between 31 and 32):

2 3 5 7 11 13 17 19 23 29 31

Starting with the first prime number (2) we divide n by these primes until we find a prime that divides n. In this case it is 7 (1001 = 7 x 143). So now we now that 143 is either the largest prime factor of 1001 or it has prime factors greater than or equal to 7. Therefore replacing n by 143 and starting from 7 we look for a factor for n in our list. We find that it is 11 (143 = 11 x 13). 13 is prime (it is in our list), so we now have our answer.

The Delphi coding for this algorithm (for the number 600851475143) is this:

procedure TfrmMain.Problem3;
  original, p: int64;
  currentIndex: integer;
  original := 600851475143;
  GetPrimeList(trunc(sqrt(original)) + 1);
  currentIndex := 0;
  p := int64(lstPrimes.Items[currentIndex]);
    if original mod p = 0 then
      original := original div p
    else begin
      p := int64(lstPrimes.Items[currentIndex]);
  until (original = 1) or (currentIndex = lstPrimes.Count);

Line 6 sets the value of the original number. Line 7 populates a list of prime numbers up to the square root of 600851475143. Line 8 starts with the first element in this list (Delphi starts counting lists from the element 0). The variable p is then initialised with the value for this element. The original number is divided by p; if the original number is divisible by p, the original number is replaced by the result of dividing it by p else p is set to be the next prime number in the list. The loop continues until the original number becomes 1 or we run out of prime numbers in our list.

Running this code produces the answer almost instantly.

Tags: ,

Comments are closed.