Sieve of Eratosthenes algorithm: Efficient way to find prime numbers

First, lets find prime numbers in following manner, which tries to divide each number, say n, by each integer i, where 2<= i <= n/2.

Below code finds the prime numbers between 2 and 10,00,000.

    private static void findPrime() {
        int count = 0;
        int num = 1000000;
        for (int i = 2; i <= num; i++) {
            count = 0;
            for (int j = 2; j <= i / 2; j++) {
                if (i % j == 0) {
                    count++;
                    break;
                }
            }
            if (count == 0) {
                System.out.println(i);
            }
        }
    }

Above code took 64 seconds (64,575 msecs) when executed on my machine.

Now following is the Java implementation of Sieve of Eratosthenes algorithm to find prime numbers.
It assumes each number to be prime and then tries to eliminate the non-prime ones. Below is the java implementation:

    public static void findPrimeBySieve() {
        int num = 1000000;
        // initially assume all integers are prime
        boolean[] isPrime = new boolean[num + 1];
        for (int i = 2; i <= num; i++) {
            isPrime[i] = true;
        }

        // mark non-primes <= N using Sieve of Eratosthenes
        for (int i = 2; i * i <= num; i++) {

            // if i is prime, then mark multiples of i as nonprime
            // suffices to consider mutiples i, i+1, ..., N/i
            if (isPrime[i]) {
                for (int j = i; i * j <= num; j++) {
                    isPrime[i * j] = false;
                }
            }
        }

        // count primes
        int primes = 0;
        for (int i = 2; i <= num; i++) {
            if (isPrime[i]){
                System.out.println(i);
                primes++;
            }
        }
        System.out.println("The number of primes <= " + primes);
    }

Execution time of above code was only 0.5 seconds (529 msecs) on my machine, i.e., 128 times faster for finding prime numbers between 2 and 1000000.

Hope you liked the post. Connect at +Java Territory  to stay tuned with latest updates.