import java.util.LinkedList; import java.util.List; import java.util.stream.Collectors; import java.util.stream.IntStream; /** * 4 different methods to search prime numbers in range * Method 1 - the worst one * Method 3 with boolean array the best one */ public class FindPrimes { public static void main(String[] args) { long before; int max = 100000; before = System.currentTimeMillis(); //findPrimesInRange(max); System.out.println("Searching primes 1 method time " + (System.currentTimeMillis() - before)); before = System.currentTimeMillis(); findPrimesInRange2(max); System.out.println("Searching primes 2 method time " + (System.currentTimeMillis() - before)); before = System.currentTimeMillis(); findPrimesInRange3(max); System.out.println("Searching primes 3 method time " + (System.currentTimeMillis() - before)); before = System.currentTimeMillis(); findPrimesInRange4(max); System.out.println("Searching primes 4 method time " + (System.currentTimeMillis() - before)); } /** * Search for primes in range from 2 to MAX param * * @param max max search range * @return list of prime values */ static List findPrimesInRange(int max) { return IntStream.rangeClosed(2, max).filter(FindPrimes::isPrime).boxed().collect(Collectors.toList()); } static boolean isPrime(int value) { for (int i = 2; i < value; i++) { if (value % i == 0) { return false; } } return true; } static List findPrimesInRange2(int max) { return IntStream.rangeClosed(2, max).filter(FindPrimes::isPrime2).boxed().collect(Collectors.toList()); } static boolean isPrime2(int value) { int valueSqrt = (int) Math.sqrt(value); for (int i = 2; i <= valueSqrt; i++) { if (value % i == 0) { return false; } } return true; } /** * Method returns boolean array index with value true means prime number * e.q. array[11] = true, number 11 is prime * * @param max max search range * @return boolean array */ static boolean[] findPrimesInRange3(int max) { boolean[] primes = new boolean[max + 1]; init(primes); int prime = 2, prev = 0; while (prime <= max) { crossValues(prime, primes); if (prime == prev || prime > (int) Math.sqrt(max)) { break; } prev = prime; prime = findNextPrime(prime, primes); } return primes; } private static int findNextPrime(int prime, boolean[] flags) { for (int i = prime + 1; i < flags.length; i++) { if (flags[i]) return i; } return prime; } private static void crossValues(int prime, boolean[] flags) { for (int i = prime * prime; i < flags.length; i += prime) { flags[i] = false; } } private static void init(boolean[] flags) { for (int i = 2; i < flags.length; i++) { flags[i] = true; } } /** * Method returns list with prime numbers, searching starts from 3 every iteration 2 numbers * Number is prime if is not divisible by previous primes * e.q checking 11 -> if is not divisible by 2,3,5,7 (previous primes) then it is prime * * @param max max search range * @return list of prime numbers */ static List findPrimesInRange4(int max) { List primes = new LinkedList<>(); primes.add(2); for (int i = 3; i <= max; i += 2) { if (isPrime3(i, primes)) { primes.add(i); } } return primes; } static boolean isPrime3(int value, List primes) { for (int i : primes) { if (value % i == 0) { return false; } if (i >= (int) Math.sqrt(value)) { return true; } } return true; } }

Methods to search prime numbers