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;

        }

    }

}

Read full article from largest prime factor of a number - 我的博客 - ITeye技术网站