largest prime factor of a number

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

What is the largest prime factor of the number 600851475143 ?

暴力解法：

const long numm = 600851475143;
long largestFact = 0;
 
for (long i = 2; i * 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;
        }
    }
}

 

更优的解法：

Any integer greater than 1 is either a prime number, or can be written as a unique product of prime numbers (ignoring the order).

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.

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.

 

Actually we can improve it a bit, by changing

counter++;

with

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.

文章来自：

http://www.mathblog.dk/project-euler-problem-3/