ex2.c

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


/* Private; Implements the sieve of Erathostenes algorithm
 * in parallel.
 *
 */
void sieveOfErathostenes(int n) {
  int i, k;
  char prime[n+1]; 

  const char unmarked = (char)0;
  const char   marked = (char)1;
  
  for (i=2;i<n+1;i++) prime[i]=unmarked; //0 and 1 are not primes
  
  

  #pragma omp parallel private(i,k) shared(prime, n)
  #pragma omp parallel for schedule(dynamic)
  for (i = 2; i <= (int)sqrt(n); i++) 
    if (prime[i]==unmarked)
      for (k=i*i; k<=n; k+=i)
        prime[k] = marked;
  

  

  int sum=0;
  int largest=0;


  for (i=2;i<n+1;i++) //0 and 1 are not primes
    if(prime[i]==unmarked) {
      sum++;
      largest=i;
    }

  
  printf("Marked primes: %d\n", sum);
  printf("Largest prime: %d\n", largest);
}


int main (int argc, char *argv[]) {
  
  int N = 8000000;
  clock_t start, end;
  double elapsed;

  
  /* input error checking */
  if (N<0) {
    printf("Input error\n");
    printf("I can't work with negative numbers\n");
    exit(0);
  }
  if (N<2) {
    printf("Marked primes: 0\n");
    printf("Largest prime: There are no primes in range\n");
    exit(0);
  }
  
  start = clock();
  sieveOfErathostenes(N);
  end = clock();
  elapsed = ((double) (end - start)) / CLOCKS_PER_SEC;

  printf("Time elapsed: %f\n", elapsed);

  exit(0);
}