Last active
May 5, 2016 14:11
-
-
Save edalorzo/4c013510d46167ab680f7a5c566144c4 to your computer and use it in GitHub Desktop.
Infinite Primes Generator
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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