/* File: primes2.cpp
   Uses openmp to speed up elapsed time.

   compile with: g++ primes2.c -o primes2 -fopenmp
   to get timing, run with: time ./primes2

*/

#include <stdio.h>
#include <omp.h>
#include <math.h>


// deliberately slow algorithm for checking primality
//
int isPrime (unsigned int n) {
   unsigned int m = sqrt(n) ;

   for (unsigned int k=2 ; k <= m ; k++) {
      if (n % k == 0) return 0 ;
   }
   return 1 ;
}


int main() {

   int numPrimes=0 ;
   const int n=10000000 ;   // 10 million

   #pragma omp parallel shared(numPrimes) 
   {
      #pragma omp for  schedule(static,32) reduction(+:numPrimes)
      for(int i=2 ; i < n ; i++) {
         if ( isPrime(i) )  numPrimes++  ;
      }
   }  // end parallel region

   printf("Number of primes less than %d is %d\n", n, numPrimes) ;


   return 0 ;
}