Project Euler Problem #3 - largest prime factor 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 &lt; numbers.length; i++)
{
    numbers[i] = i+1;
}

//determining which numbers are prime numbers
for(int i = 0; i &lt;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 &gt; 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 &lt; pf.length; p++)
{
    System.out.println(pf[p]);
}*/


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

System.out.println(primeFactor);
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 &lt; 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 &lt; 10000; n += 2) { // only odd numbers can be primes (except 2)
  bool isAPrime = true;
  for (int i = 0; i &lt; 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:


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


Example 2:


Factorization of the number 13. Bound is floor(13/2) = 6.
First prime is 2. Not a factor.
Next candidate 3 is prime, not a factor.
Next candidate 5 is prime, not a factor.
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