Project Euler #3 - checking only up to sqrt(input)

Question

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<limit;count++)
    {
        if(numbers[count]==true)
        {
            for(int i=2;i*count<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 <= limit; count++)
    {
        // if count is a prime number
        if (numbers[count])
        {
            // set all multiples of count to false
            for (int i = 2; i * count <= 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?

Answer 1

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 < limit; count++) {
        if (numbers[count]) {
            for (int i = 2; i * count < 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:

1. Start from d = 2
2. Divide the target number by d as many times as possible without remainder
3. 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 > 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 > target) {
            return target;
        }

Answer 2

You ask a general algorithmic question in addition to the code review, so I'll answer with a lazy pseudocode:

Divisors(n) = [d | d in [2..(n-1)], n % d == 0] 
            // all d in a list from 2 to (n-1) such that n % d == 0, or IOW
            = let { q = Sqrt(n)
                  ; divs = [(d, n/d) | d in [2..(q-1)], n % d == 0] 
                  } // list of pairs of divisiors,  d < sqrt(n)  and  n/d > sqrt(n) 
              in
                 Map(first, divs)            // the first components of pairs, and
                  `Append` [q | q*q == n]    // a sqrt of n, if n is a perfect square,
                  `Append` Reverse( Map(second, divs))   // and the second components

So you see, all divisors of a number are found by trying the divisions only up to the square root of that number, because if d is a divisor of n, then automatically (n / d) is a divisor of n as well (if n = a*b, a <= b, then a*a <= b*a i.e. a*a <= n).

The first of thus found factors is guaranteed to be prime, by construction (we tried, unsuccessfully, all the smaller ones, right? if it weren't prime, its prime factors would be divisors as well, and we would find the smallest of them, earlier).

So if Divisors(n) starts with a d, so does PrimeDivisors(n), and then

PrimeDivisors(n) = case Take(1, Divisors(n))
                     of [d] -> [d] `Append` PrimeDivisors(n/d)
                     of []  -> [n | n > 1] // n has no divisors, so it's a prime, itself

where all the found divisors are prime by construction, and need not be tested for primality, at all. As to the data structure, linked list will do - if you'd like to collect all the prime factors that is. Or you can just ignore all of them except the last one, kept just in a variable, in effect implementing Append as a `Append` b = b, so you end up with just a loop like in @janos's answer.