#
All Primes

/*************************************************************************** * Author: Isai Damier * Title: All Primes * Project: geekviewpoint * Package: algorithms * * Statement: * Given a number n, return all prime numbers less than or equal to n. * * Sample Input: 35 * Sample Output: {2,3,5,7,11,13,17,19,23,29,31} * * Time Complexity of Solution: * Best = Average = Worst = O(Time) = O(n log log n), * where n is the max number to test. You can verify this as * O(Time) = n/p1+n/p2+... = n*sum(1/p) for all prime p < n^0.5 * * Approach: * Arithmetic review: * 0) 0 and 1 are not prime numbers. * 1) The first prime number is 2. * 2) A number is prime if it is only divisible by itself and by 1 * 3) If y is the square root of x (i.e. y^2 = x); then if x is not * divisible by any number between 2 and y inclusive, then x is prime. * * This is an "innocent until proven guilty" algorithm that capitalizes on * the above arithmetic facts to find all primes between 2 and n. In the * innocent until proven guilty paradigm, all candidates start out as * winners. Then through a rigorous process, the algorithm winnows the * faulty candidates until the elite is left. Known as the sieve of * Eratosthenes, there are a number of ways to implement the set of * arithmetic rules above into an algorithm. The following is easy to * understand. * * 0] Declare a bit vector and initialize all the keys from 0 to * x with the value 'true' -- making them all primes. * 1] For keys 0 and 1, set the values to false * 2] For each number n between 2 and x, set all multiples of n to false. * 3] Group together all keys whose values are still true and * return that group. * * There are a number of ways to improve the time complexity of this * program, such as considering only odd numbers as opposed to all * numbers between 2 and n. **************************************************************************/ public List<Integer> allPrimes(int max) { if (2 > max) { return null; } boolean[] primes = new boolean[max + 1]; Arrays.fill(primes, true); primes[0] = primes[1] = false; for (int i = 2, sqrt = (int) Math.sqrt(max); i <= sqrt; i++) { if (primes[i]) { for (int k = 2; k * i <= max; k++) { if (primes[k * i]) { primes[k * i] = false; } } } } List<Integer> result = new ArrayList<Integer>(); for (int i = 2; i <= max; i++) { if (primes[i]) { result.add(i); } } return result; }

import java.util.Arrays; import java.util.List; import org.junit.Test; import static org.junit.Assert.*; public class NumbersTest { /** * Test of allPrimes method, of class Numbers. */ @Test public void testAllPrimes() { System.out.println("allPrimes"); int max = 0; Numbers primes = new Numbers(); List<Integer> expected = Arrays.asList( new Integer[] {2,3,5,7,11,13,17,19,23,29}); assertTrue(expected.equals(primes.allPrimes(30))); expected = Arrays.asList( new Integer[] {2,3,5,7,11,13,17,19,23,29,31}); assertTrue(expected.equals(primes.allPrimes(31))); expected = Arrays.asList( new Integer[] {2,3,5,7,11,13,17,19,23,29,31,37}); assertTrue(expected.equals(primes.allPrimes(40))); } }