Optimized way to find count of Prime Number existence between 1 to N

  A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.  A natural number greater than 1 that is not a prime number is called a composite number. For example, 5 is prime because 1 and 5 are its only positive integer factors.  whereas 6 is composite because it has the divisors 2 and 3 in addition to 1 and 6.

Single-threaded implementation to find Prime Number Between 1 to N where N can be any positive Number.

 static int getNumberOfPrimes(int n) {  
          List<Integer> primeNumberList = new ArrayList<>();       
          int counter = 0;  
          boolean isNotPrime = false;  
          Long startTime = System.nanoTime();  
          if(n>2){  
               primeNumberList.add(2);  
               counter++;  
          }  
          for(int i=3; i<=n; i=i+2){  
               isNotPrime = false;  
               for(int k:primeNumberList){  
                    if(k<=Math.sqrt(i) && i%k==0){  
                isNotPrime = true;  
                break;  
                    }  
               }  
            if(!isNotPrime){  
                 primeNumberList.add(i);  
              counter++;  
            }  
          }  
          System.out.println("Total Execution Time::"+(System.nanoTime()-startTime)+" nanosec");  
          return counter;  
        }  

Above program was executed to find prime number between 1 to 1000000 in corei5 processor.
It took near about 47 sec to find prime number between 1 to 1000000.

In Order to optimize the above program, I used multi-threading and the result is just amazing. It gives the count of prime number between 1 to N (i.e. 1000000) within a second.

Mutli-thread implementation to find Prime Number Between 1 to N where N can be any positive Number.

 import java.util.concurrent.Callable; 
 
 public class PrimeNumber implements Callable<Integer> {  
      private int startRange;  
      private int endRange;  
      public PrimeNumber() {  
           // TODO Auto-generated constructor stub  
      }  
      public PrimeNumber(int startRange, int endRange) {  
           this.startRange = startRange;  
           this.endRange = endRange;  
      }  
      @Override  
      public Integer call() throws Exception {  
     int counter = 0;  
     boolean isNotPrime = false;  
     if(startRange%2==0)  
          startRange++;  
     if(startRange < 2 && endRange > 2){  
          startRange = 3;       
          counter++;  
     }  
     for(int i=startRange; i<endRange; i+=2){  
          isNotPrime = false;  
          for(int j=3; j<=Math.sqrt(i); j+=2){  
               if(i%j == 0){  
                    isNotPrime = true;  
                       break;  
               }  
          }  
          if(!isNotPrime){  
         counter++;  
       }  
     }  
     return counter;  
      }  
 }  

Test Class for execution of above mutli-thread program

 import java.util.ArrayList;  
 import java.util.List;  
 import java.util.concurrent.Callable;  
 import java.util.concurrent.ExecutionException;  
 import java.util.concurrent.ExecutorService;  
 import java.util.concurrent.Executors;  
 import java.util.concurrent.Future;

  
 public class PrimeNumberTest {  
      public static void main(String[] args) throws InterruptedException, ExecutionException {  
           List<Callable<Integer>> todo = new ArrayList<Callable<Integer>>();       
           ExecutorService executor = Executors.newFixedThreadPool(6);  
           int upperRange = 1000000;  
           Long startTime = System.nanoTime();  
           for(int i=1; i<=upperRange; i+=100000){  
                if(upperRange < 100000){  
                     todo.add(new PrimeNumber(i,upperRange));  
                }else{  
                     todo.add(new PrimeNumber(i,i+100000));  
                }  
           }  
           int sum = 0;  
           List<Future<Integer>> answers = executor.invokeAll(todo);  
           executor.shutdown();  
           for(Future<Integer> taskResult: answers){  
                sum+=taskResult.get();  
           }  
           System.out.println("Total PrimeNumber between 1 to "+upperRange+" is "+sum);  
           System.out.println("Total Execution Time::"+(System.nanoTime()-startTime));  
      }  
 }