Prime Sieve of Eratosthenes: Find all primes smaller than or equal to n.

Sample Code:

package com.rizvi.so;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
// Java program to print all primes smaller than or equal to
// n using Sieve of Eratosthenes

class SieveOfEratosthenes {
    void sieveOfEratosthenes(int n) {
        int counter = 0;
        // Create a boolean array "prime[0..n]" and initialize
        // all entries it as true. A value in prime[i] will
        // finally be false if i is Not a prime, else true.
        boolean prime[] = new boolean[n + 1];
        List<Integer> primeList = new ArrayList<Integer>();
        for (int i = 0; i < n; i++)
            prime[i] = true;

        for (int p = 2; p * p <= n; p++) {
            // If prime[p] is not changed, then it is a prime
            if (prime[p] == true) {
                // Update all multiples of p
                for (int i = p * p; i <= n; i += p) {
                    prime[i] = false;
                }
            }
        }

        // Print all prime numbers
        for (int i = 2; i <= n; i++) {
            if (prime[i] == true) {
//                System.out.println(i + " ");
                primeList.add(i);
                counter++;
            }
        }
        // Show the primes from primeList
//        for(Integer primeVal : primeList) {
//            System.out.println(""+primeVal);
//        }

        System.out.println("Total number of primes: " + counter);
        System.out.println("Total number of primeList: " + primeList.size());
    }

    // Driver Program to test above function
    public static void main(String args[]) {
        Scanner asdf = new Scanner(System.in);
        int n = asdf.nextInt();
        long startTime = System.nanoTime();
        System.out.print("Following are the prime numbers ");
        System.out.println("smaller than or equal to " + n);
        SieveOfEratosthenes g = new SieveOfEratosthenes();
        g.sieveOfEratosthenes(n);
        long estimatedTime = System.nanoTime() - startTime;
        System.out.println();
        System.out.println("Total time taken: " + estimatedTime);
    }
}

// This code has been contributed by Amit Khandelwal.
// http://www.geeksforgeeks.org/sieve-of-eratosthenes/

Output:

100000000
Following are the prime numbers smaller than or equal to 100000000
Total number of primes: 5761455
Total number of primeList: 5761455

Total time taken: 8097239106