# 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 + " ");
}
}
}
}
```