Introduction:

A prime number is a natural number greater than 1 having only two factors – 1 and the number itself. For eg: 2, 3, 5, 7, 11 etc are all prime numbers.

Numbers that are not prime are known as composite numbers.

In this tutorial, we’ll learn how to generate all prime numbers less than or equal to a given number.

Generating Prime Numbers:

1. Brute – Force Approach:

A brute-force solution to generate all prime numbers less than or equal to a specified number would be to iterate through the entire range and do a primality test for each number within that range:

List<Integer> generatePrimeNumbers(int number) {
    List<Integer> listOfPrimes = new ArrayList<>();
    if(number >= 2)
        listOfPrimes.add(2);
    for(int num = 3; num <= number; num++) {
        if(isPrime(num))
            listOfPrimes.add(num);
    }    
    return listOfPrimes;
}

//Generic Implementation of isPrime()
boolean isPrime(int number) {
    if(number == 2) return true;
    if(number < 2 || number % 2 == 0) return false;
    for(int div = 3; div * div <= number; div += 2) {
        if(number % div == 0)
            return false;
    }
    return true;
}    

Note that we have used the isPrime() method we covered in our number primality test tutorial.

Time Complexity : O(n*sqrt(n))

2. Sieve Of Eratosthenes:

There’s is a popular algorithm known as “Sieve of Eratosthenes” to help us generate prime numbers less than a given number n in just O(n * log(log n)) time.

Algorithm :

1. Maintain a list of natural numbers from 2 to n, all unmarked initially.
2. Initially p = 2, the smallest prime number.
3. Cross-out/mark all the multiples of p in the list (excluding the number p itself).
4. Pick next unmarked number greater than p from the list, name it as p (it will be a prime number, otherwise would have been crossed-off previously) and repeat step – 2. Repeat this process until we have reached the end of the list.

The remaining unmarked numbers in the list are all prime numbers in that range.

 Demonstration of Sieve of Eratosthenes:

Example: Finding all prime numbers less than 30.

Java Implementation:

Let’s now try and implement this algorithm in Java:

List<Integer> generatePrimeNumbersUsingSieve(int number) {
    boolean[] sieve = new boolean[number + 1];
    Arrays.fill(sieve, true);
    sieve[0] = sieve[1] = false;

    for(int val = 2; val*val <= number; val++){
        if(sieve[val]) {
            //mark all its unmarked multiples
            for(int count = 2; count * val <= number; count++) {
                if(sieve[count*val]) 
                    sieve[count*val] = false;
            } 
        }  
    }

    //make a list of all prime numbers
    List<Integer> listOfPrimes = new ArrayList<>();
    for(int index = 2; index <= number; index++) {
        if(sieve[index])
             listOfPrimes.add(index);
    }
    return listOfPrimes;
}

The implementation is simple. We start off by marking all the numbers as prime. We further go on reducing that list using Sieve of Eratosthenes algorithm.

Note that we have made further optimizations to the solution:

1. We have only traversed up to sqrt(number). 
2. We have used a boolean array instead of an int array to optimize the space consumption. The index of our boolean array represents the number. It means sieve[3] = true means number 3 is a prime number, sieve[4] = false represents 4 is not a prime number & so on.

3. Conclusion:

In this tutorial, we have explored ways in which we can generate all prime numbers up to a given number N.

We covered Sieve of Eratosthenes algorithmic implementation which helps us do it very efficiently and can be used for quite large values of N.