Sign in to follow this  
Infinity95

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


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this