GitHub Account Google Scholar Account LinkedIn Account Twitter Account flickr Account vialab Research Group Profile Page

Generating Prime Numbers

Date: May 19, 2016
There are many ways to generate prime numbers. The naive way is to employ trial division. Instead of checking if the prime number candidate is divisible by numbers up to the candidate itself, one can reduce the time complexity of this algorithm by only checking up to and including the square root of the candidate. This is because all composite numbers (non-primes) that are less than the candidate must have a factor that is less than or equal to the square root of the candidate.

The sieve of Eratosthenes and the sieve of Sundaram are two better algorithms for generating prime numbers, and their implementations are shown below. For information on other prime number generation algorithms, you can check out the sieve of Atkin and wheel factorization. There are also many different ways to check for primality including the Miller–Rabin primality test, the Solovay–Strassen primality test, the Baillie–PSW primality test, the Fermat (probable) primality test, and the AKS primality test.
import java.util.Scanner;
import java.util.Arrays;

public class PrimeNumbers {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int max = in.nextInt();

        calcPrimesLoop(max);
        System.out.println("");

        calcPrimesRecurse(max);
        System.out.println("");

        sieveEratosthenes(max);
        System.out.println("");

        sieveSundaram(max);
        System.out.println("");
    }

    public static void sieveSundaram(int max) {

        max = (max / 2) - 1;
        boolean[] array = new boolean[max + 1];
        Arrays.fill(array, true);

        int i = 1;
        int j = 1;

        while (j + (2 * j) <= max) {

            int nonPrime = i + j + (2 * i * j);

            if (nonPrime <= max) {
                array[nonPrime] = false;
            }

            if (i < j) {
                i++;

            } else {
                j++;
                i = 1;
            }
        }

        System.out.print(2 + " ");

        for (int index = 1; index <= max; index++) {

            if (array[index]) {
                System.out.print( ((index * 2) + 1) + " ");
            }
        }
    }

    public static void sieveEratosthenes(int max) {

        boolean[] array = new boolean[max + 1];
        Arrays.fill(array, true);

        int prime = 2;
        int counter = 2;

        while (true) {

            int nonPrime = prime * counter;

            if (nonPrime <= max) {
                array[nonPrime] = false;
                counter++;

            } else {

                counter = 2;
                boolean nextPrime = false;
                int sqrt = (int) Math.sqrt(max);

                for (int i = prime + 1; i <= sqrt; i++) {

                    if (array[i]) {
                        nextPrime = true;
                        prime = i;
                        break;
                    }
                }

                if (!nextPrime) {
                    break;
                }
            }
        }

        for (int i = 2; i <= max; i++) {

            if (array[i]) {
                System.out.print(i + " ");
            }
        }
    }

    public static void calcPrimesLoop(int max) {

        if (max < 2) {
            return;
        }

        for (int num = 2; num <= max; num++) {

            boolean isPrime = true;
            int sqrt = (int) Math.sqrt(num);

            for (int div = 2; div <= sqrt; div++) {

                if (num % div == 0) {
                    isPrime = false;
                }
            }

            if (isPrime) {
                System.out.print(num + " ");
            }
        }
    }

    public static void calcPrimesRecurse(int candidate) {

        if (candidate < 2) {
            return;
        }

        int sqrt = (int) Math.sqrt(candidate);
        boolean isPrime = checkPrime(candidate, sqrt);

        if (isPrime) {
            System.out.print(candidate + " ");
        }

        calcPrimesRecurse(--candidate);

    }

    public static boolean checkPrime(int candidate, int divisor) {

        if (candidate == 2 || divisor < 2) {
            return true;

        } else if (candidate % divisor == 0
            || candidate % 2 == 0) {

            return false;

        } else {

            divisor--;

            if (divisor >= 2) {
                return checkPrime(candidate, divisor);
            }

            return true;
        }
    }
}