My C code doesn't output anything, or end running

Question

I'm trying to answer this question:

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

What is the largest prime factor of the number 600851475143 ?

Here is my code:

#include <stdio.h>

int isPrime(long long num)
{
    for (long long k = 1; k < num; k++)
    {
            if (num%k == 0)
                    return 0;
    }

    return 1;
} 
long long num = 600851475143;
int main(void)
{
    long long prime_factor = 0;
    for (long long j = 2; j < num; j++)
    {
            if (num % j == 0 && isPrime(j) == 1)
                    prime_factor = j;
    }

    printf("%lli\n", prime_factor);


}

But for some reason it doesn't print anything, or even end. What is causing this?

Answer 1

That's a terribly inefficient way of finding the prime factors of a number.

To find the prime factors, you should:

1. Create a static list of primes less than or equal to (number / 2).
2. Iterate over each element in the list of primes and see if each one can evenly divide the number.
3. Divide the original number by the prime, and check the last number again.

Why? Well the smallest prime is 2. If the number isn't even then the first prime that can divide any number > 2 is 3.

Every number can be uniquely identified by its prime factors. This is called the Fundamental Theorem of Arithmetic. That means that there is only one way to represent e.g. 15 as a product of primes, in this case { 3, 5 }.

However any prime can divide a number more than once. For example, 49 is the product of two primes { 7, 7 }. Dividing the original number by one of its factors makes subsequent divisions quicker. And you can logically stop checking when the number == 1.