Jump to content
  • Advertisement
Sign in to follow this  
Infinity95

project euler problem 03

This topic is 1770 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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!