Friday, July 13, 2018

How do write an algorithm to print prime number ?

Problem statement:
Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.

Example:

Input : n =10 
Output : 2 3 5 7 
Input : n = 20 
Output: 2 3 5 7 11 13 17 19
  1. public class PrimeNumberSeries {
  2.     public static void main(String arg[]) {
  3.         primeNumberSeries(10);
  4.     }
  5.     public static void primeNumberSeries(int n) {
  6.         // Create a boolean array "prime[0..n]" and initialize all entries it as            //true. A value in prime[i] will finally be false if i is Not a prime, else true
  7.         boolean prime[] = new boolean[n + 1];
  8.         for (int i = 0; i < n; i++) {
  9.             prime[i] = true;
  10.         }
  11.         for (int p = 2; p * p <= n; p++) {
  12.             if (prime[p] == true) {
  13.                 // update all multiple of p
  14.                 for (int i = p * 2; i <= n; i = i + p) {
  15.                     prime[i] = false;
  16.                 }
  17.             }
  18.         }
  19.         // print all prime numbers
  20.         for (int i = 2; i <= n; i++) {
  21.             if (prime[i] == true) {
  22.                 System.out.print(i + " ");
  23.             }
  24.         }
  25.     }
  26. }
output:
2 3 5 7 

No comments:

Post a Comment

Blueprint for self-improvement

To learn faster: Make the process fun To understand yourself : Write To understand the world better : Read To build deeper connection : Lis...