Project Euler #3 - checking only up to sqrt(input) I know it's possible for the largest factor of a number to be greater than the sqrt (e.g., for 14, 7 is the largest). Why then does almost every solution for the problem check only up to the square root? Also, I have a nagging feeling that boolean[] is not the best data structure to use here, since in this case the number is much smaller than the size of the array. What alternative data structure would be recommended in this case?

public static int largestPrime(long n)
{
    int limit=(int)Math.sqrt(n)+1;
    boolean [] numbers = new boolean[limit];
    Arrays.fill(numbers,true);
    int largestPrimeFactor=1;
    for(int count=2;count&lt;limit;count++)
    {
        if(numbers[count]==true)
        {
            for(int i=2;i*count&lt;limit;i++)
                numbers[count*i]=false;
            if(n%count==0)
                largestPrimeFactor=count;
        }

    }
    return largestPrimeFactor;
}


Edit: Hmm, looks like it's incorrect to only check for primes up to the square root of the input (at least without checking if the complementary factor is prime). 

This is what I originally wanted to implement, but the number was too large to create a boolean array of that size. 

public static int largestPrime(int n)
{
    int largestPrime = 2;
    // Worse case scenario: largest prime n is divisible by is itself
    int limit = n;
    // Create an boolean array of index up to n
    boolean[] numbers = new boolean[limit + 1];
    Arrays.fill(numbers, true);

    for (int count = 2; count &lt;= limit; count++)
    {
        // if count is a prime number
        if (numbers[count])
        {
            // set all multiples of count to false
            for (int i = 2; i * count &lt;= limit; i++)
                numbers[count * i] = false;
            // Check if the input number is divisible by count
            if (n % count == 0)
            {
                // The largest possible prime is the complementary factor
                limit = n / count;
                largestPrime = count;
            }
        }
    }
    return largestPrime;
}


I guess my second question is, is there a better alternative to a boolean array, and if not, what to change in the program so that it works with large numbers?
This implementation is not correct: for your example 14 it incorrectly returns 2 instead of 7.

You don't need to check == true of boolean expressions, you can use them directly, for example:

if (numbers[count]) { ... }


The formatting doesn't follow Java standards. In Eclipse, if you select your function and press Control-Shift-f it will change it this, which is more pleasant to read:

public static int largestPrime(long n) {
    int limit = (int) Math.sqrt(n) + 1;
    boolean[] numbers = new boolean[limit];
    Arrays.fill(numbers, true);
    int largestPrimeFactor = 1;
    for (int count = 2; count &lt; limit; count++) {
        if (numbers[count]) {
            for (int i = 2; i * count &lt; limit; i++) {
                numbers[count * i] = false;
            }
            if (n % count == 0) {
                largestPrimeFactor = count;
            }
        }
    }
    return largestPrimeFactor;
}


A simple way to fix the implementation is to re-implement following the same logic you do in math class:


Start from d = 2
Divide the target number by d as many times as possible without remainder
Increment d, return to step 2, until target is reduced to 1


This is pretty simple, correct, without using a boolean array:

public static long largestPrimeFactor(long n) {
    long d = 2;
    long target = n;
    while (target &gt; 1) {
        while (target % d == 0) {
            target /= d;
        }
        ++d;
    }
    return d - 1;
}


To make this faster, after the ++d you can insert this check:

        if (d * d &gt; target) {
            return target;
        }