Java Reference
In-Depth Information
primes[1] = 3L;
// and the second
int count = 2;
// Count of primes found-up to
now,
// which is also the array
index
long number = 5L;
// Next integer to be tested
outer:
for( ; count < primes.length; number += 2L) {
// The maximum divisor we need to try is square root of number
long limit = (long)ceil(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] == 0L) {
// Is it an exact divisor?
continue outer;
// Yes, so try the next number
}
}
primes[count++] = number;
// We got one!
}
for(long n : primes) {
System.out.println(n);
// Output all the primes
}
}
MorePrimes.java
This program computes as many prime numbers as the capacity of the
primes
array allows.
How It Works
Any number that is not a prime must be a product of prime factors, so you 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 2 * 12, 3 * 8, 4 * 6; then you come to cases
where the first factor is greater than the square root so the second is less, 6 * 4, 8 * 3, and so on, and so
you are repeating the pairs of factors you already have.
You first declare the array
primes
to be of type
long
and define it as having 20 elements. You set the
first two elements of the
primes
array to 2 and 3, respectively, to start the process off, as you use the
primes you have in the array as divisors when testing a new candidate.
The variable
count
is the total number of primes you have found, so this starts out as 2 because you have
already stored 2 and 3 in the first two elements of the primes array. Note that because you use
count
as
the
for
loop control variable, you omit the first expression between parentheses in the loop statement, as
the initial value of
count
has already been set.
You store the candidate to be tested in
number
, with the first value set as 5. The
for
loop statement
labeled
outer
is slightly unusual. First of all, the variable
count
that determines when the loop ends is
not incremented in the
for
loop statement, but in the body of the loop. You use the third control expres-
