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;
var
original, p: int64;
currentIndex: integer;
begin
original := 600851475143;
GetPrimeList(trunc(sqrt(original)) + 1);
currentIndex := 0;
p := int64(lstPrimes.Items[currentIndex]);
repeat
if original mod p = 0 then
original := original div p
else begin
inc(currentIndex);
p := int64(lstPrimes.Items[currentIndex]);
end;
until (original = 1) or (currentIndex = lstPrimes.Count);
ShowMessage(IntToStr(p));
end;
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: Mathematics, Project Euler