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*.

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))

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 :**

- Maintain a list of natural numbers from 2 to
*n,*all unmarked initially. - Initially p = 2, the smallest prime number.
- Cross-out/mark all the multiples of
*p*in the list (excluding the number p itself). - 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.

**Example:** Finding all prime numbers less than 30.

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:

- We have only traversed up to
*sqrt(number).* - 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.

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.

Be the First to comment.