Java: Print all primes smaller than or equal to any given number
Java Math Exercises: Exercise-20 with Solution
In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.
Write a Java program to print all primes smaller than or equal to any given number.
Sample Solution:
Java Code:
import java.util.*;
public class solution {
private static int [] generatePrimes(int num) {
boolean[] temp = new boolean[num + 1];
for (int i = 2; i * i <= num; i++) {
if (!temp [i]) {
for (int j = i; i * j <= num; j++) {
temp [i*j] = true;
}
}
}
int prime_nums = 0;
for (int i = 2; i <= num; i++) {
if (!temp [i]) prime_nums++;
}
int [] all_primes = new int [prime_nums];
int index = 0;
for (int i = 2; i <= num; i++) {
if (!temp [i]) all_primes [index++] = i;
}
return all_primes;
}
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.print("Input the number: ");
int n = scan.nextInt();
if (n>0)
{
int [] result = generatePrimes(n);
System.out.println("Prime numbers <= " + n +": "+ Arrays.toString(result));
}
}
}
Sample Output:
Input the number: 125 Prime numbers <= 125: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]
Flowchart:
Java Code Editor:
Contribute your code and comments through Disqus.
Previous: Write a Java program to generate a magic square of order n.
Next: Write a Java program to find the number which has the maximum number of distinct prime factors in a given range.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics