Find all prime numbers less than or equal to N in Java

In this Java tutorial, we will write a program to find all prime numbers less than or equal to N. We will use the concept of Sieve of Eratosthenes.

Sieve of Eratosthenes

It is an ancient method for generating prime numbers smaller than a given number in mathematics. It is one of the most efficient methods for finding primes smaller than a given number. A number which is only divisible by 1 and itself is a prime number. Hence, this method uses the idea that any multiple of a prime number will not be a prime number. So, we iteratively mark the multiples of a prime (starting from 2) as a composite or not a prime number. Let us look at the algorithm:

• Create a boolean array of size equal to the given upper limit number (N).
• We mark each position in the array as true starting from 2.
• Then initialize a number to 2. If it is prime then mark each multiple of number as false until the multiplication is less than N.
• Repeat step 2 till number becomes equal to square root of N.
• Then the elements in the array with true values contains all prime numbers.

Program to find all prime numbers smaller than N in Java

import java.util.Scanner;


public class FindPrimes {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        boolean[] primes = new boolean[n + 1];

        for (int i = 2; i <= n; i++) {
            primes[i] = true;
        }

        int sqrt = (int) Math.sqrt(n);
        int num = 2;
        while (num <= sqrt) {
            if (primes[num]) {
                int mul = num;

                while (mul * num <= n) {
                    primes[mul * num] = false;
                    mul++;
                }
            }
            num++;
        }

        System.out.println("Primes less than or equal to " + n);

        for (int i = 2; i <= n; i++) {
            if (primes[i]) {
                System.out.print(i + " ");
            }
        }
    }
}

You can also read:

• Java Program To Check A Number Is Prime or Not
• Factorial of a large number using BigInteger in Java
• Check A Number Is Armstrong or Not Using Java Program