# 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<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?

• If one of the factors of a number is larger than the square root, then the complamentary factor(s) are necessarily smaller than the square root (14/7 == 2). This is why you only have to check only up to the square root. – Rotem Oct 26 '14 at 5:36
• But the aim is to ry and find the largest prime factor the number is divisible by. Doesn't that mean it's necessary to check if the complementary factors are prime too, which greatly slows down the computation? – Ellyl Oct 26 '14 at 17:32
• Since the original function was reviewed, you may post that added code as a new question instead. – Jamal Oct 28 '14 at 6:36

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;
}

• Thanks for the tip about boolean and formatting. Why return target if d*d is greater than target? Is target guaranteed to be prime? – Ellyl Oct 26 '14 at 18:42
• Yes, it's guaranteed to be a prime :) Think about it, while you are dividing a number going from smaller primes to larger, when you find a number whose square would be bigger than the target, there cannot possible be another number between d and target. Consider 230: divide by 2 to get 115; ++d until next divisor, 5; divide by 5 to get 23; no need to ++d anymore, because 5 * 5 = 25 > 23, so there cannot be another number between 5 and 23 that can divide 23 without remainder – janos Oct 26 '14 at 18:48
• Thank you (I would +rep if I could)! That answers my questions of why it it's necessary to check primes up to sqrt(n). With my implementation, any array element that is still true after looping to sqrt(n) numbers must be prime. I must then check if n is divisible by those primes. I do think your code is still faster though :D – Ellyl Oct 27 '14 at 5:23
• this is incorrect, with that test d * d > target inserted after ++d, -- for 125 it will return 1. – Will Ness Nov 2 '14 at 21:23
• I've written an explanation of the same idea that explores the alternatives as well. – 200_success Nov 3 '14 at 8:44

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.