Skip to content

Instantly share code, notes, and snippets.

@edalorzo
Last active May 5, 2016 14:11
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save edalorzo/4c013510d46167ab680f7a5c566144c4 to your computer and use it in GitHub Desktop.
Save edalorzo/4c013510d46167ab680f7a5c566144c4 to your computer and use it in GitHub Desktop.
Infinite Primes Generator
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.function.LongPredicate;
import java.util.function.LongSupplier;
import java.util.stream.LongStream;
/**
* Primes generator.
*/
public class Primes {
private final Map<Long,Boolean> cache;
private final LongPredicate isPrime;
/**
* Creates a new basic prime generator.
*/
public Primes(){
this.cache = Collections.emptyMap();
this.isPrime = Primes::isPrime;
}
/**
* Creates a memoized prime generator with a cache of
* the provided size.
*
* @param cacheSize - the cache size.
*/
public Primes(int cacheSize) {
if(cacheSize < 1) {
throw new IllegalArgumentException("The cache size must be a positive integer bigger than 0: " + cacheSize);
}
this.cache = new HashMap<>(cacheSize);
this.isPrime = memoize(Primes::isPrime);
}
private LongPredicate memoize(LongPredicate source) {
return x -> cache.computeIfAbsent(x, source::test);
}
private static boolean isEven(long n){
return n % 2 == 0;
}
/**
* Determines the smallest divisor of n starting at k.
*/
private static long ldf(long n, long k) {
while(true){
if(n % k == 0) return k;
else if(k * k > n) return n;
else k = k + 2;
}
}
private static boolean isPrime(long n) {
return n==2 || ((n >= 2) && !isEven(n) && ldf(n, 3) == n);
}
/**
* Infinite generator of prime numbers.
*/
private static class PrimeGenerator implements LongSupplier {
private long prime = 2;
private final LongPredicate isPrime;
PrimeGenerator(LongPredicate isPrime) {
this.isPrime = isPrime;
}
@Override
public long getAsLong() {
if(prime == 2) {
return prime++;
}
while(true){
long next = prime;
prime = prime + 2;
if(isPrime(next)){
return next;
}
}
}
}
/**
* Provides an infinite stream of prime numbers.
*/
public LongStream stream(){
return LongStream.generate(new PrimeGenerator(this.isPrime));
}
/**
* Usage example
*/
public static void main(String[] args) {
Primes primes = new Primes();
primes.stream().limit(30).forEach(n -> System.out.printf("%d ", n));
System.out.println();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment