Tuesday, June 11, 2013

Euler Project Question #3

Euler Project Question #3
Find Prime:
We can use the Fundamental Theorem of Arithmetic which states:
Any integer greater than 1 is either a prime number, or can be written as a unique product of prime numbers (ignoring the order).




started from below

Example:
The number 12.
We start with the smallest prime number (2).
12/2 = 6, which means that 2 is a prime factor to 12.
We try again to divide the remainder with 2 again:
6/2 = 3. Three is a prime number as well, so we now have the complete factorization which is
Prime factorization of 12 is 2,2,3 and we can check that 2*2*3=12.
A more elaborate explanation can be found here
We make a logical short cut here and realise that we don’t need to find all prime numbers first, we can “just” enumerate through all numbers until we have a complete factorization if we start from below, since all non-prime factors will already be factorized in primes, as a consequence of the proof given in the link to the theorem. Lets write some code shall we.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const long numm = 600851475143;
long newnumm = numm;
long largestFact = 0;
int counter = 2;
while (counter * counter < newnumm) {
    if (newnumm % counter == 0) {
        newnumm = newnumm / counter;
        largestFact = counter;
    } else {
        counter++;
    }
}
if (newnumm > largestFact) { // the remainder is a prime number
    largestFact = newnumm;
}
We start with 2, and check how many times that number is divisible with the remainder we have. Once 2 is not a divisor to the remainder we increase the counter by one and check 3, 4 and so on. If 4 was a factor to the original number, 2 will be a factor at least twice as well. And then we can go on, until the counter is larger than the square root of the remainder.
If the remainder is different from one, then the remainder is also a prime factor. However I only need to check if it is larger than the largest factor found, to see if it is interesting. This code executes below measurable time on my computer.
1
2
The largest primefactor of 600851475143 is: 6857
Solution took 0 ms
Actually we can improve it a bit, by changing
1
counter++;
with
1
counter = (counter == 2) ? 3 : counter + 2;
Which is a compressed if construct. If the counter is two, we increase it to 3, otherwise we increase it by 2 so we only check 2 and the odd numbers. It doesn’t really make much of a difference for the execution speed of this problem.
I hope that these notes has taught you something, and triggered your curiosity to explore further.

No comments:

Post a Comment