Project Euler #3 – Largest Prime Factor

Problem Overview

• We are given a large number, typically 600851475143.


• Goal: Find the largest prime factor of this number.


• Example with a smaller number:
  • Let n = 13195.
  • Its prime factors are 5, 7, 13, 29.
  • The largest prime factor is 29.

C Solution

#include <stdint.h>
#include <stdio.h>

#ifndef N
#define N (600851475143ul)
#endif // N

uint64_t solve(uint64_t n)
{
    uint64_t largestPrimeFactor = 0;

    // 1. remove factor 2 ( all the even factors will be eliminated).
    while (n % 2 == 0)
    {
        largestPrimeFactor = 2;
        n /= 2;
    }

    // 2. test odd factors (not necessarily prime) at 3, 5, 7, ...
    for (uint64_t i = 3; i * i <= n; i += 2)
    {
        while (n % i == 0)
        {
            largestPrimeFactor = i;
            n /= i;
        }
    }

    // 3. if n > 1 then n itself is the largest prime factor of @arg {N}.
    if (n > 1)
    {
        largestPrimeFactor = n;
    }

    return largestPrimeFactor;
}

int main()
{
    fprintf(stdout, "The largest prime factor of the number %lu is %lu\n", N, solve(N));
    return 0;
}

1. High-Level Idea


• We successively divide out prime factors from n until it is reduced to 1 or to a remaining prime.
• At each step, we remember the most recent factor that divided n — that factor is a candidate for “largest prime factor”.
• By starting from small factors and moving upward, the last factor we record will be the largest prime factor.



2. Handling the Factor 2



while (n % 2 == 0)
{
    largestPrimeFactor = 2;
    n /= 2;
}

• First, we take care of the only even prime, 2.
• While n is even, we divide it by 2 and record 2 as the current largest prime factor.
• After this loop, n is guaranteed to be odd, so we can skip all even candidates later.



3. Testing Odd Factors



for (uint64_t i = 3; i * i <= n; i += 2)
{
    while (n % i == 0)
    {
        largestPrimeFactor = i;
        n /= i;
    }
}

• We check odd potential factors i starting from 3, incrementing by 2 each time: 3, 5, 7, 9, ...
• The condition i * i <= n is a common optimization:
  • If n still has a composite factor, at least one of its prime factors will be ≤ √n.
  • Once i * i > n, any remaining n must be prime.
• Inner loop:
  • While i divides n, divide it out and record i as largestPrimeFactor.
  • This removes all copies of i (e.g., if n had i^k as a factor).



4. Remaining Prime Factor



if (n > 1)
{
    largestPrimeFactor = n;
}

• After the loop, if n > 1, the remaining n itself is prime.
• Because we removed small factors in increasing order, this leftover prime must be the largest prime factor.



5. main and Configurable N



#ifndef N
#define N (600851475143ul)
#endif // N

• N defaults to 600851475143ul, the number given in the original problem.
• You can override it at compile time, for example:

  gcc -DN=13195 euler3.c -o euler3
  ./euler3
  

• main simply prints the result:

  int main()
  {
      fprintf(stdout, "The largest prime factor of the number %lu is %lu\n", N, solve(N));
      return 0;
  }
  




6. Complexity


• In the worst case, the loop over odd i runs up to about √n, giving time complexity roughly O(√n).
• In practice this is fast enough for a single 64-bit number, especially in C.
• Memory usage is constant: we only keep a few 64-bit integers.