Sunday, November 29, 2015

Project Euler – Problem 3 - largest prime factor of a number

largest prime factor of a number - 我的博客 - ITeye技术网站
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
http://www.mathblog.dk/project-euler-problem-3/
http://www.mathsisfun.com/prime-factorization.html

`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.
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.

`const` `long` `numm = 600851475143;`
`long` `largestFact = 0;`
`long``[] factors = ``new` `long``[2];`

`for` `(``long` `i = 2; i * i < numm; i++) {`
`    ``if` `(numm % i == 0) { ``// It is a divisor`
`        ``factors[0] = i;`
`        ``factors[1] = numm / i;`

`        ``for` `(``int` `k = 0; k < 2; k++) {`
`            ``bool` `isPrime = ``true``;`
`            ``for` `(``long` `j = 2; j * j <  factors[k]; j++) {`
`                ``if` `(factors[k] % j == 0) {`
`                    ``isPrime = ``false``;`
`                    ``break``;`
`                 ``}`
`             ``}`
`             ``if` `(isPrime && factors[k] > largestFact) {`
`                ``largestFact = factors[k];`
`            ``}`
`        ``}`
`    ``}`
`}`

Brute Force:
1. const long numm = 600851475143;
2. long largestFact = 0;
3.
4. for (long i = 2; i * i < numm; i++) {
5.     if (numm % i == 0) { // It is a divisor
6.         bool isPrime = true;
7.         for (long j = 2; j < i; j++) {
8.             if (i % j == 0) {
9.                 isPrime = false;
10.                 break;
11.             }
12.         }
13.         if (isPrime) {
14.             largestFact = i;
15.         }
16.     }
17. }

`const` `long` `numm = 600851475143;`
`long` `largestFact = 0;`

`for` `(``long` `i = 2; i < numm; i++) {`
`    ``if` `(numm % i == 0) { ``// It is a divisor`
`        ``bool` `isPrime = ``true``;`
`        ``for` `(``long` `j = 2; j < i; j++) {`
`            ``if` `(i % j == 0) {`
`                ``isPrime = ``false``;`
`                ``break``;`
`            ``}`
`        ``}`
`        ``if` `(isPrime) {`
`            ``largestFact = i;`
`        ``}`
`    ``}`
`}`