Project Euler

Problem 3: Largest Prime Factor

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600,851,475,143 ?

The Catch

How to find the prime factors of any number.
How to determine if the factor is prime.
How to store 600,851,475,143 in Java, since maximum value for int primitive type is 2,147,483,647.

The Light

Use prime factorization to find an arbitrary x's prime factors:

• Divide x by first prime number p (2 is the first value for p).
• If x is not divisible by p, move to the next prime that x is divisible by.
• If x is divisible by p, then keep dividing x by p until x is no longer divisible by p or x gets reduced to 1, whichever comes first.
• Repeat step 2 and 3 until x gets reduced to 1.
  

Example: Prime factorize 14.

• 14 / 2 = 7
• 7 % 2 != 0
• 7 % 3 != 0
• 7 % 5 != 0
• 7 / 7 = 1
• Primes factor of 14 are 2, 7.

Determine primeness: Recall that a prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Prime numbers are always odd with the exception of 2, the smallest prime number. So the first criteria for a number x to be prime is x needs to be an odd, natural number that is greater than 2. We then have to check all of its factors up to the square root of x. The reason for this is for every factor a of x that is less than or equal to sqrt(x), there is a corresponding factor b of x that is greater than sqrt(x) such that a * b = x, thus checking for b is redundant.

Example: Is 17 a prime number? 17 is obviously an odd number. If 17 has any more factors other than 1 and itself, then it is not prime. Prime factorize 17 to find its factors: 17 is not divisible by 2, 3, 5, 7, 11, and 13, thus 2, 3, 5, 7, 11, and 13 are not its factors. So 17's only factors are 1 and 17, making 17 prime. In fact, we can stop prime factorizing at sqrt(17), or 4.123 because if 17 is not divisible by any number a with 1 < a <= 4.123, then 17 will not be divisible by any number b with 4.123 < b < 17.

To store the number 600,851,475,143, use primitive type long, whose maximum value is 9,223,372,036,854,775,807.

The Code

public class Problem3
{
  public static void main(String[] args)
  {
    long n = 600851475143L;  //Use literal L at the end of the number to let the compiler know you're using a long
    int factor = 3;

    while(n > 1)
    {
      if(isPrime(factor))
        if(n % factor == 0)
          n /= factor;	
        else
          factor += 2;		
      else
        factor += 2;
    }
    System.out.println("Greatest prime factor = " + factor);
  }

  public static boolean isPrime(int n)
  {
    if(n < 2)
      return false;

    if(n != 2 && n % 2 == 0)
      return false;

    for(int i = 3; i*i <= n; i += 2)
    {
      if(n % i == 0)
        return false;
    } 
    return true;
  }
}