Sieve of Eratosthenes | GeeksforGeeks

Sieve of Eratosthenes | GeeksforGeeks
Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.

The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so.

Java code:

http://www.codebytes.in/2015/01/fast-ranged-prime-number-generation.html

Code from http://leetcode.com/2010/04/finding-prime-numbers.html

void prime_sieve(int n, bool prime[]) {

  prime[0] = false;

  prime[1] = false;

  int i;

  for (i = 2; i <= n; i++)

    prime[i] = true;

  int limit = sqrt(n);

  for (i = 2; i <= limit; i++) {

    if (prime[i]) {

      for (int j = i * i; j <= n; j += i)

        prime[j] = false;

    }

  }

}

1. Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

When the algorithm terminates, all the numbers in the list that are not marked are prime.

// marks all mutiples of 'a' ( greater than 'a' but less than equal to 'n') as 1.

void markMultiples(bool arr[], int a, int n)

{

    int i = 2, num;

    while ( (num = i*a) <= n )

    {

        arr[ num-1 ] = 1; // minus 1 because index starts from 0.

        ++i;

    }

}

// A function to print all prime numbers smaller than n

void SieveOfEratosthenes(int n)

{

    // There are no prime numbers smaller than 2

    if (n >= 2)

    {

        // Create an array of size n and initialize all elements as 0

        bool arr[n];

        memset(arr, 0, sizeof(arr));

        /* Following property is maintained in the below for loop

           arr[i] == 0 means i + 1 is prime

           arr[i] == 1 means i + 1 is not prime */

        for (int i=1; i<n; ++i)

        {

            if ( arr[i] == 0 )

            {

                //(i+1) is prime, print it and mark its multiples

                printf("%d ", i+1);

                markMultiples(arr, i+1, n);

            }

        }

    }

}

http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Java

public class Sieve{
    public static LinkedList<Integer> sieve(int n){
        LinkedList<Integer> primes = new LinkedList<Integer>();
        BitSet nonPrimes = new BitSet(n+1);
        for (int p = 2; p <= n ; p = nonPrimes.nextClearBit(p+1)) {
            for (int i = p * p; i <= n; i += p)
                nonPrimes.set(i);
            primes.add(p);
        }
        return primes;
    }
}

public class Sieve{
       public static LinkedList<Integer> sieve(int n){
               if(n < 2) return new LinkedList<Integer>();
               LinkedList<Integer> primes = new LinkedList<Integer>();
               LinkedList<Integer> nums = new LinkedList<Integer>();
 
               for(int i = 2;i <= n;i++){ //unoptimized
                       nums.add(i);
               }
 
               while(nums.size() > 0){
                       int nextPrime = nums.remove();
                       for(int i = nextPrime * nextPrime;i <= n;i += nextPrime){
                               nums.removeFirstOccurrence(i);
                       }
                       primes.add(nextPrime);
               }
               return primes;
       }
}

To optimize by testing only odd numbers, replace the loop marked "unoptimized" with these lines:

nums.add(2);
for(int i = 3;i <= n;i += 2){
       nums.add(i);
}

Infinite iterator with a very fast page segmentation algorithm (sieves odds-only)

Although somewhat faster than the previous infinite iterator version, the above code is still over 10 times slower than an infinite iterator based on array paged segmentation as in the following code, where the time to enumerate/iterate over the found primes (common to all the iterators) is now about half of the total execution time:

http://yuanhsh.iteye.com/blog/2173077
Don't use this: inefficient:

1. public static long nthPrimeNumber(int n) {  
2.     long[] primes = new long[n];  
3.     primes[0] =  2;  
4.     primes[1] =  3;  
5.     primes[2] =  5;  
6.     primes[3] =  7;  
7.     primes[4] = 11;  
8.     primes[5] = 13;  
9.   
10.     int i = 6;  
11.     for (long x = primes[i-1] + 2; i < n; x += 2) {  
12.         if(isPrime(x, primes)) primes[i++] = x;  
13.     }  
14.     return primes[n - 1];  
15. }  
16.   
17. private static boolean isPrime(long p, long[] primes) {  
18.     long max = (long) Math.ceil(Math.sqrt(p));  
19.     for (long divisor : primes) {  
20.         if (divisor > max) break;  
21.         if (p % divisor == 0) return false;  
22.     }  
23.     return true;  
24. } 

http://blog.giovannibotta.net/2012/03/segmented-sieve-of-eratosthenes-in-java.html

http://www.zrzahid.com/prime-numbers-less-than-equal-to-n-in-on-time/

public boolean isPrime(int n) {  
   if (n < 2) return false;  
   if (n == 2) return true;  
   if ((n & 1) == 0) return false;  
   
   int rootN = (int)Math.sqrt(n);  
   for (int i=2; i<=rootN; ++i) {  
     if (n % i == 0) return false;  
   }  
   return true;  
 } 

public static Set<Integer> allPrimes(final int N) {
    final boolean[] flag = new boolean[N];
    final Set<Integer> primes = new TreeSet<Integer>();

    for (int i = 0; i < N; i++) {
        flag[i] = true;
    }

    for (int i = 0; i < Math.sqrt(N); i++) {
        if (flag[i] == true) {
            primes.add(i);
            for (int j = i * i; j < N; j += i) {
                flag[j] = false;
            }
        }
    }

    return primes;
}

Read full article from Sieve of Eratosthenes | GeeksforGeeks