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(;

        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;

        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:

2 responses to “Find all prime numbers less than or equal to N in Java”

  1. Sergiu D says:

    thank you it was very helpful!!!
    the only thing I’ve added was
    System.out.println(“Please input number “); on Line 7

  2. kidus says:

    can you write a Java program that accepts a +ve integer n and finds all the prime numbers less or
    equal to n. Your program should handle all possible exceptions.

Leave a Reply

Your email address will not be published. Required fields are marked *