# 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

## Leave a Reply