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:
thank you it was very helpful!!!
the only thing I’ve added was
System.out.println(“Please input number “); on Line 7
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.