115 lines
3.4 KiB
Java
115 lines
3.4 KiB
Java
import java.util.*;
|
|
|
|
public class PrimeGenerator {
|
|
private int limit_;
|
|
private int index_ = 0;
|
|
private int increment_;
|
|
private int count_ = 0;
|
|
private List<Integer> primes_ = new ArrayList<>();
|
|
private BitSet sieve_ = new BitSet();
|
|
private int sieveLimit_ = 0;
|
|
|
|
public PrimeGenerator(int initialLimit, int increment) {
|
|
limit_ = nextOddNumber(initialLimit);
|
|
increment_ = increment;
|
|
primes_.add(2);
|
|
findPrimes(3);
|
|
}
|
|
|
|
public int nextPrime() {
|
|
if (index_ == primes_.size()) {
|
|
if (Integer.MAX_VALUE - increment_ < limit_)
|
|
return 0;
|
|
int start = limit_ + 2;
|
|
limit_ = nextOddNumber(limit_ + increment_);
|
|
primes_.clear();
|
|
findPrimes(start);
|
|
}
|
|
++count_;
|
|
return primes_.get(index_++);
|
|
}
|
|
|
|
public int count() {
|
|
return count_;
|
|
}
|
|
|
|
private void findPrimes(int start) {
|
|
index_ = 0;
|
|
int newLimit = sqrt(limit_);
|
|
for (int p = 3; p * p <= newLimit; p += 2) {
|
|
if (sieve_.get(p/2 - 1))
|
|
continue;
|
|
int q = p * Math.max(p, nextOddNumber((sieveLimit_ + p - 1)/p));
|
|
for (; q <= newLimit; q += 2*p)
|
|
sieve_.set(q/2 - 1, true);
|
|
}
|
|
sieveLimit_ = newLimit;
|
|
int count = (limit_ - start)/2 + 1;
|
|
BitSet composite = new BitSet(count);
|
|
for (int p = 3; p <= newLimit; p += 2) {
|
|
if (sieve_.get(p/2 - 1))
|
|
continue;
|
|
int q = p * Math.max(p, nextOddNumber((start + p - 1)/p)) - start;
|
|
q /= 2;
|
|
for (; q >= 0 && q < count; q += p)
|
|
composite.set(q, true);
|
|
}
|
|
for (int p = 0; p < count; ++p) {
|
|
if (!composite.get(p))
|
|
primes_.add(p * 2 + start);
|
|
}
|
|
}
|
|
|
|
private static int sqrt(int n) {
|
|
return nextOddNumber((int)Math.sqrt(n));
|
|
}
|
|
|
|
private static int nextOddNumber(int n) {
|
|
return 1 + 2 * (n/2);
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
PrimeGenerator pgen = new PrimeGenerator(20, 200000);
|
|
System.out.println("First 20 primes:");
|
|
for (int i = 0; i < 20; ++i) {
|
|
if (i > 0)
|
|
System.out.print(", ");
|
|
System.out.print(pgen.nextPrime());
|
|
}
|
|
System.out.println();
|
|
System.out.println("Primes between 100 and 150:");
|
|
for (int i = 0; ; ) {
|
|
int prime = pgen.nextPrime();
|
|
if (prime > 150)
|
|
break;
|
|
if (prime >= 100) {
|
|
if (i++ != 0)
|
|
System.out.print(", ");
|
|
System.out.print(prime);
|
|
}
|
|
}
|
|
System.out.println();
|
|
int count = 0;
|
|
for (;;) {
|
|
int prime = pgen.nextPrime();
|
|
if (prime > 8000)
|
|
break;
|
|
if (prime >= 7700)
|
|
++count;
|
|
}
|
|
System.out.println("Number of primes between 7700 and 8000: " + count);
|
|
int n = 10000;
|
|
for (;;) {
|
|
int prime = pgen.nextPrime();
|
|
if (prime == 0) {
|
|
System.out.println("Can't generate any more primes.");
|
|
break;
|
|
}
|
|
if (pgen.count() == n) {
|
|
System.out.println(n + "th prime: " + prime);
|
|
n *= 10;
|
|
}
|
|
}
|
|
}
|
|
}
|