Infinity95 324 Report post Posted July 20, 2013 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)) { } } 0 Share this post Link to post Share on other sites
Waterlimon 4398 Report post Posted July 20, 2013 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. 2 Share this post Link to post Share on other sites
Infinity95 324 Report post Posted July 20, 2013 Ah i got it now. Actuall quite easy ;) Just needed a little help to get there. 0 Share this post Link to post Share on other sites
Paradigm Shifter 5832 Report post Posted July 21, 2013 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). 0 Share this post Link to post Share on other sites
Infinity95 324 Report post Posted July 21, 2013 I would have to change return NULL; to return num i guess. That should fix it. 0 Share this post Link to post Share on other sites