erastotenes.c

/*
* Adapted from: http://w...content-available-to-author-only...s.org/sieve-of-eratosthenes
*/


/*

sequencial:

5761455

real    0m4.053s
user    0m3.977s
sys 0m0.068s

paralelo:

5761455

real    0m3.105s
user    0m5.662s
sys 0m0.072s

speedup user = 1,4166

*/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
#include <omp.h>

int sieveOfEratosthenes(int n)
{
   omp_set_num_threads(2);
   // 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.
   int primes = 0;
   bool *prime = (bool*) malloc((n+1)*sizeof(bool));
   int sqrt_n = sqrt(n);
   int nt = 0;

   memset(prime, true,(n+1)*sizeof(bool));

   for (int p=2; p <= sqrt_n; p++)
   {
       // If prime[p] is not changed, then it is a prime
       if (prime[p] == true)
       {
           // Update all multiples of p
           #pragma omp parallel for
           for (int i=p*2; i<=n; i += p)
               prime[i] = false;
       }
    }

    // count prime numbers
    #pragma parallel for reduction(+:primes)
    for (int p=2; p<=n; p++)
       if (prime[p])
         primes++;

    return(primes);
}

int main()
{
   int n = 100000000;
   printf("%d\n",sieveOfEratosthenes(n));
   return 0;
}