Project Euler Problem #3 - largest prime factor

Question

I have began doing the problems found on Project Euler and have just solved problem 3. However, I feel as if my code is very long and too brute-force. I was hoping somebody could give it a look and give me some guidelines for this problem and for future programming in general. This would help me with cleaning it up or even just revealing better ways of solving this.

Problem 3 states:

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

What is the largest prime factor of the number 600851475143?

int primeFactor = 0;
int pfCounter = 0;
int[] pf = new int [1229];
int[] numbers = new int[10000];
long number = 600851475143L;
int p = 0;

//initialize the array numbers to include all numbers
//from 1 to 1000 for determining prime numbers
for(int i = 0; i < numbers.length; i++)
{
    numbers[i] = i+1;
}

//determining which numbers are prime numbers
for(int i = 0; i <numbers.length; i++)
{           
    //divide each number by every number below it
    //to see if the pfCounter = 1 which would mean
    //it is only divisible by itself and 1
    for(int j = i; j > 0; j--)
    {
        if(numbers[i] % j == 0)
        {
            pfCounter++;
        }
    }

    //if the number only has 1 in it's pfCounter
    //insert the number from the numbers array into the 
    //pf array and restart the counter to 0 else restart 
    //the counter to 0 and try again
    if(pfCounter == 1)
    {
        pf[p] = numbers[i];
        pfCounter = 0;
        p++;
    }
    else
    {
        pfCounter = 0;
    }

}

/*
for(p = 0; p < pf.length; p++)
{
    System.out.println(pf[p]);
}*/


for(int i = 0; i < pf.length; i++)
{
    if(number % pf[i] == 0)
    {
        primeFactor = pf[i];
    }
}

System.out.println(primeFactor);

Answer 1

If a number x (with x > 2) is not a prime number, there exists a prime p so that x is divisible by p and p < x.

This means to determine if a number is a prime number, you only have to test it against smaller primes (which you already know). We need one prime (2) to start this process, so we will begin to search for primes from 3 onward.

This technique is known as memoization, which you will find quite useful for many PE problems.

This would lead to the following code (incorporating the points of GameDroids):

int[] primes = new int[somethingSufficientlyLarge];
primes[0] = 2;
primeCounter = 1; // a "pointer" to the next prime

for (int n = 3; n < 10000; n += 2) { // only odd numbers can be primes (except 2)
  bool isAPrime = true;
  for (int i = 0; i < primeCounter; i++) {
    if (n % primes[primeCounter] == 0) {
      isAPrime = false;
      break;
    }
  }
  if (isAPrime) {
    primes[primeCounter] = n;
    primeCounter++
  }
}

Note that using a (Linked) List will make hardcoding the length of the prime array unneccessary. However, there may or may not be performance implications.

But you do not know that the largest prime factor is in fact smaller than 10000. It could be ⌊600851475143/2⌋ for all we know. This would be the proper bound of your search space.

Maybe we can reduce that bound: Every time we find a prime in our sieve loop, we test if number is divisible by that prime. We then do so until the number isn't divisible by that factor. If the result is 1, we can break the loop, as the largest prime factor was found. The loop runs from 2 to bound, where bound initially is floor(number/2), but once the first factor is found, the bound is the number divided by every factor. If no factor was found, then the number itself is the largest factor.

Example 1:

1. Factorization of the number 15. Bound is floor(15/2) = 7.
2. First prime is 2. Not a factor.
3. Next candidate 3 is prime, is a factor. New bound is 5.
4. Next candidate 5 is prime, is a factor. Bound drops to 1 → break.
5. Largest prime factor is 5.

Example 2:

1. Factorization of the number 13. Bound is floor(13/2) = 6.
2. First prime is 2. Not a factor.
3. Next candidate 3 is prime, not a factor.
4. Next candidate 5 is prime, not a factor.
5. Loop exits without factor found. 13 itself must be a prime, and its largest prime factor.

General hints:

• In your original code you tested for factors in the range (0, n] where n is the number you wanted to factorize. But as no factor can be larger than n/2, you could have reduced the range to (0, ⌊n/2⌋]. This would have reduced substantial overhead. Try to find such cases that can never occur (factors in the range [⌈n/2⌉, n]) and optimize.

• In your fist factorization loop you started with the largest factor first. This is bad, as ½ of numbers are divisible by 2, ⅓ by 3, ⅕ by 5 and so on. I.e. you can weed out many non-primes by testing a very small set of numbers. Try to find common cases, and test for them befoe testing for uncommon cases. Also, try to “fail early” (which is wisdom not only applicable to programming).

  However, when factorizing your large number, you should have started with the largest possible prime first, count downwards, and stop once you found a factor, instead of looping through all primes

Answer 2

If I may give you one tip right away: try to write out the variable names and don't use abbreviations. If primeFactorCounter seems too long to you, just say counter. Right now your code is short and you know what pfCountermeans, but it is just hard to read for someone else or for you when you read it again in 2 Weeks.

By the way nicely documented, it was really easy to understand your code that way :)

Anyway, back to your question.

• the first for loop fills an array with the natural numbers. This is not necessary. the numbers won't change, so instead of looping through the array every time to get the number, just use the loop's index for(int i=1; i<=n; i++) where nwould be the 10000 instead of the array's length.

• another little tweak to speed things up could be to stop the loop when you find out that you have no use for the number. But you would have to change the loops conditions a little bit. You only need to test the numbers that are smaller than the one you are investigating and bigger than 1 (because every number can be divided by one or itself):

so instead of:

for (int j = i; j > 0; j--) {
  if (numbers[i] % j == 0) {
     pfCounter++;
  }
}

try

for (int j = i-1; j > 1; j--) {
  if (numbers[i] % j == 0) {
     break;   // this breaks out of the loop
  }
}

Now you don't have to test if your pfCounter is bigger than 1. (PS: I didn't replace the numbers[i] by i just start the "i-loop" with i=1and you'll be fine!

Answer 3

A complete running program to solve this problem should take well under 20 lines of Java code; any more than that and you're working too hard.

Hints:

• By inspection, 600851475143 has no even factors.

• There is no need to construct a list of primes or test any of the factors for primality. The heart of the solution is…

  for (int factor = 3; ; factor += 2) {
      while (n % factor == 0) {
          // As long as you try the factors in increasing order, 
          // factor is guaranteed to be prime at this point.
          n /= factor;
      }
      …
  }
  

That's all! You should be able to figure out the terminating condition for the loop.

(Why is that comment true? What happens if you replace the while with if?)

Answer 4

I gave up. I was wrong. try this:

import java.lang.Math;

public class largest_prime { 

    public static boolean isPrime(long N) {
        if (N <= 3) return N > 1;
        if (!(N%6==1 || N%6==5)) return false;
        long sqr = (long)Math.sqrt(N) + 1;
        for (long k6=5; k6 <= sqr; k6+=6) 
            if (N%k6==0 || N%(k6+2)==0) return false; // just 6k±1  
        return true;
    }

    public static long gpf(long n) { // Greatest Prime Factor
        long p,q;
        long ans=0;
        while(n%2 ==0) { 
            n/=2;
            ans = 2;
        }
        while (n%3==0) {
            n/=3;
            ans = 3;
        }
        for (p=5;p<=(long)n/2+1;p+=6) { 
            q = p+2;
            while(n % q == 0) {
                n/=q;
                ans=q;
            }
            while(n % p == 0) {
                n/=p;
                ans=p;
            }
            if (isPrime(n)) return n;
        }
         
        // ans is prime return it
        return ans; 
    }

    public static void main(String args[]) { 
        long number = 600851475143L;
        long primeFactor = 0;
        primeFactor = gpf(number);
        System.out.println(primeFactor);
    }

}

Output:

6857