Java Reference
In-Depth Information
Try It Out - Even More Primes
Try out the following code derived, in part, from the code we used in Chapter 2.
public class MorePrimes {
public static void main(String[] args) {
long[] primes = new long[20]; // Array to store primes
primes[0] = 2; // Seed the first prime
primes[1] = 3; // and the second
int count = 2; // Count of primes found - up to now,
// which is also the array index
long number = 5; // Next integer to be tested
outer:
for( ; count < primes.length; number += 2) {
// The maximum divisor we need to try is square root of number
long limit = (long)Math.ceil(Math.sqrt((double)number));
// Divide by all the primes we have up to limit
for(int i = 1; i < count && primes[i] <= limit; i++) {
if(number%primes[i] == 0) { // Is it an exact divisor?
continue outer;
// Yes, try the next number
}
}
primes[count++] = number; // We got one!
}
for(int i=0; i < primes.length; i++)
System.out.println(primes[i]); // Output all the primes
}
}
This program computes as many prime numbers as the capacity of the array
primes
will allow.
How It Works
Any number that is not a prime must be a product of prime factors, so we only need to divide a prime
number candidate by prime numbers that are less than or equal to the square root of the candidate to
test for whether it is prime. This is fairly obvious if you think about it. For every factor a number has
that is greater than the square root of the number, the result of division by this factor is another factor
that is less than the square root. You perhaps can see this more easily with a specific example. The
number 24 has a square root that is a bit less than 5. You can factorize it as 2x12, 3x8, 4x6, then we
come to cases where the first factor is greater than the square root so the second is less, 6x4, 8x3 etc.,
and so we are repeating the pairs of factors we already have.
We first declare the array
primes
to be of type
long
, and define it as having 20 elements. We set the
first two elements of the
primes
array to 2 and 3 respectively to start the process off, as we will use the
primes we have in the array as divisors when testing a new candidate. The variable,
count
, is the total
number of primes we have found, so this starts out as 2. Note that we use
count
as the
for
loop
counter, so we omit the first expression between parentheses in the loop statement as
count
has
already been set.
