Project Euler Problem #3 - largest prime factor
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