Skip to content

Instantly share code, notes, and snippets.

@offchan42
Last active November 20, 2015 08:55
Show Gist options
  • Save offchan42/e4751475d7bfa7415fe0 to your computer and use it in GitHub Desktop.
Save offchan42/e4751475d7bfa7415fe0 to your computer and use it in GitHub Desktop.
Prime Generator with sorted list as a cache source
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.IntStream;
/**
* Created by off999555 on 20/11/2558 at 14:27.
*/
public class TestStreamPrimeGenerator {
static List<Integer> primes = new ArrayList<>(Arrays.asList(2, 3, 5)); // using list instead of tree set to enhance performance
public static void main(String[] args) {
IntStream.iterate(3000, n -> n + 1)
.filter(TestStreamPrimeGenerator::isPrime)
.limit(200)
.forEach(System.out::println);
}
private static boolean isPrime(int n) {
int index = Collections.binarySearch(primes, n);
if (index >= 0) return true;
int last = primes.get(primes.size() - 1);
if (n < last) return false;
int sqrt = (int) Math.sqrt(n);
while (last < sqrt) {
//noinspection StatementWithEmptyBody
while (!isPrime(last += 2)) ;
primes.add(last);
}
int ceiling = Collections.binarySearch(primes, sqrt);
if (ceiling < 0) ceiling = ~ceiling; // if the sqrt is not found,
// it will return the -(insertion index)-1 which need to be negated
return IntStream.range(0, ceiling).map(primes::get).noneMatch(prime -> n % prime == 0);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment