Proxy > Gmail Facebook Yahoo!

23.Write a sieve program.



import java.util.*;

public class PrimeSieve {
 
  public static void main(String[] args) {
    Scanner scan=new Scanner(System.in);
    System.out.println("Enter No of limit(n)");
    int N = scan.nextInt();
   
    // initially assume all integers are prime
    boolean[] isPrime = new boolean[N + 1];
    for (int i = 2; i <= N; i++) {
      isPrime[i] = true;
    }
   
    // mark non-primes <= N using Sieve of Eratosthenes
    for (int i = 2; i*i <= N; i++) {
     
      // if i is prime, then mark multiples of i as nonprime
      // suffices to consider mutiples i, i+1, ..., N/i
      if (isPrime[i]) {
        for (int j = i; i*j <= N; j++) {
          isPrime[i*j] = false;
        }
      }
    }
   
    // count primes
    int primes = 0;
    for (int i = 2; i <= N; i++) {
      if (isPrime[i]) primes++;
    }
    System.out.println("The number of primes <= " + N + " is " + primes);
  }
}




Responses

0 Respones to "23.Write a sieve program."


Send mail to your Friends.  

Expert Feed

 
Return to top of page Copyright © 2011 | My Code Logic Designed by Suneel Kumar