• Advertisement
Sign in to follow this  

project euler problem 03

This topic is 1648 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
print ('answer is', n)

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement