The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

**Running time:** Unknown, never finishes

**Assessment:** Brute forced, naive, ugly, doesn’t finish. *It was really hard to post this as-is without self-editing to make me look less like a nub, but the point of posting these is to show the evolution of thought processes and problem-solving over time.*

The answer is displayed more or less right away, but the code never exits, so you’re not sure if the last answer displayed before you get annoyed and hit Ctrl-C is the correct one. (It is.) I never had the patience to let it finish, let alone measure the runtime. I would approach the problem completely differently–as you’ll see in some of the later factorization examples–if I were to re-write it today.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream> using namespace std; long long is_prime(long long n) { //returns 0 if not prime, 1 if prime if (n % 2 == 0) return 0; // is even, therefore not prime for (long long i = 3; i <= ((n / 2) + 1); i += 2) // Skip all the even numbers { if (n % i == 0) return 0; //not prime } return 1; } long long find_bigprime(long long n) { long long factor = 0; for(long long i = 3; i <= n; i += 2) { if (n % i == 0) { if (is_prime(i)) { factor = i; cout << factor << endl; } } } return factor; } int main() { long long input = 600851475143; cout << find_bigprime(input); return 0; } |

I didnt know you could do long long…. That fixed my program!