/*
This program is a part of the companion code for Core Java 8th ed.
(http://horstmann.com/corejava)
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see .
*/
import java.util.*;
/**
* This program runs the Sieve of Erathostenes benchmark. It computes all primes up to 2,000,000.
* @version 1.21 2004-08-03
* @author Cay Horstmann
*/
public class Sieve
{
public static void main(String[] s)
{
int n = 2000000;
long start = System.currentTimeMillis();
BitSet b = new BitSet(n + 1);
int count = 0;
int i;
for (i = 2; i <= n; i++)
b.set(i);
i = 2;
while (i * i <= n)
{
if (b.get(i))
{
count++;
int k = 2 * i;
while (k <= n)
{
b.clear(k);
k += i;
}
}
i++;
}
while (i <= n)
{
if (b.get(i)) count++;
i++;
}
long end = System.currentTimeMillis();
System.out.println(count + " primes");
System.out.println((end - start) + " milliseconds");
}
}