Monday, November 30, 2015

Getting the Prime numbers using the Sieve of Eratosthenes method

Hello Guys, today we are going to look the method by which the large number of prime numbers can be calculated.

The definition of the Sieve of Eratosthenes method goes this way:
"Mark the first presence of the number as prime and mark all its multiples as non primes." - Wiki


Looking at the diagram its pretty clear to understand that the first presence of number is considered to be prime and all the multiples of it (increasing order) is marked non prime also, we will check for the prime only if the number is not marked as non prime before, like in case of 6, the number would be marked as non prime before while we run the thing for the number 2 so it is skipped in case of 3.

Now lets see the program as well, running link here

Here is the code:

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public static void main(String[] args) {
  int MAX = 1000000;
  int T = 0;
  boolean isPrime[] = new boolean[MAX];
  for(int i=2; i<isPrime.length; i++)
   isPrime[i] = true;
  
  int primes[] = new int[MAX];
  int p = 0;
  for(int i=2;i<MAX;i++){
   if(isPrime[i]){
    primes[p++] = i;
    for(int j=2*i; j<MAX; j+=i)
     isPrime[j] = false;
   }
  }
  System.out.println("All your prime numbers are calculated, just for example I am taking out the 10101th prime number");
  T = 10101;
  System.out.println(primes[T]);
    }
}

No comments:

Post a Comment