Last active
November 20, 2015 08:55
-
-
Save offchan42/e4751475d7bfa7415fe0 to your computer and use it in GitHub Desktop.
Prime Generator with sorted list as a cache source
This file contains hidden or 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.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