# project euler problem 03

## Recommended Posts

Infinity95    324

So i solved the problem and was looking through other solutions and found this:

n = 600851475143
i = 2
while i*i < n:
while n%i == 0:
n = n / i
i = i + 1


I don't really get why this solution works. Can anyone explain this to me?

BTW: This is my solution in c++:

#include <iostream>
#include <dinput.h>
#include <vector>

using namespace std;

long long largestpfactor(long long num) {
double start = sqrt(num);

for(int i = start; i > 1; i--) {
if((num % i) == 0) {
long long div = 2;

while(((i % div) != 0) && div < i) {
div++;
}

if(div == i) return i;
}
}

return NULL;
}

int main() {

cout << largestpfactor(600851475143) << endl;

while(!GetAsyncKeyState(VK_END)) {

}
}


##### Share on other sites
Waterlimon    4398

Hmm...

Imagine n is formed by some primes, like

2*2*2*2*3*7*7*11 (or something like that?)

Now, what the algorithm does, is start from the smallest prime (2) to get them out by dividing as many times as possible.

3*7*7*11

Then it increments i by 1, so it divides by 3 so that goes out too.

7*7*11

now, it will divide by 4, which is not a prime. These non-prime numbers will however have no effect, because we already took all the 2's out and 4 is 2*2 (if its not divisible by 2, it certainly wont be by 4)

then we finally get to 7, and after dividing by 7 twice we are left with 11 which is the answer.

##### Share on other sites
Infinity95    324

Ah i got it now. Actuall quite easy ;) Just needed a little help to get there.

##### Share on other sites

Does your (C++) solution work if num is prime? I was expecting to see a

return num;

somewhere if there are no prime divisors <= sqrt(num).

##### Share on other sites
Infinity95    324

I would have to change return NULL; to return num i guess. That should fix it.