10aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart/** An OpenMP example. 20aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart * Based on the example listed on the following web page: 30aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart * http://developers.sun.com/sunstudio/downloads/ssx/tha/tha_using.html 40aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart */ 50aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart 60aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart 70aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart#include <assert.h> 80aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart#include <math.h> 90aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart#include <omp.h> 100aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart#include <stdio.h> 110aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart#include <stdlib.h> 1272ab1ffbc336b17236e6f0b3f8e6919559de0de4bart#include <unistd.h> // getopt() 138f822af9b234e7c553c408eba65a641c4773457fbart#include "../../drd/drd.h" 140aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart 150aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart 160aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bartstatic int is_prime(int* const pflag, int v) 170aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart{ 180aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart int i; 190aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart int bound = floor(sqrt ((double)v)) + 1; 200aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart 210aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart for (i = 2; i < bound; i++) 220aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart { 230aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart /* No need to check against known composites */ 240aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart if (!pflag[i]) 250aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart continue; 260aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart if (v % i == 0) 270aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart { 280aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart pflag[v] = 0; 290aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart return 0; 300aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart } 310aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart } 320aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart return (v > 1); 330aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart} 340aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart 350aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bartint main(int argc, char **argv) 360aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart{ 370aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart int i; 380aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart int total = 0; 398f822af9b234e7c553c408eba65a641c4773457fbart int trace_total = 0; 4072ab1ffbc336b17236e6f0b3f8e6919559de0de4bart int silent = 0; 4172ab1ffbc336b17236e6f0b3f8e6919559de0de4bart int n; 4272ab1ffbc336b17236e6f0b3f8e6919559de0de4bart int num_threads = 2; 4372ab1ffbc336b17236e6f0b3f8e6919559de0de4bart int optchar; 440aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart int* primes; 450aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart int* pflag; 460aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart 478f822af9b234e7c553c408eba65a641c4773457fbart while ((optchar = getopt(argc, argv, "qt:v")) != EOF) 4872ab1ffbc336b17236e6f0b3f8e6919559de0de4bart { 4972ab1ffbc336b17236e6f0b3f8e6919559de0de4bart switch (optchar) 5072ab1ffbc336b17236e6f0b3f8e6919559de0de4bart { 518f822af9b234e7c553c408eba65a641c4773457fbart case 'q': 528f822af9b234e7c553c408eba65a641c4773457fbart silent = 1; 538f822af9b234e7c553c408eba65a641c4773457fbart break; 548f822af9b234e7c553c408eba65a641c4773457fbart case 't': 558f822af9b234e7c553c408eba65a641c4773457fbart num_threads = atoi(optarg); 568f822af9b234e7c553c408eba65a641c4773457fbart break; 578f822af9b234e7c553c408eba65a641c4773457fbart case 'v': 588f822af9b234e7c553c408eba65a641c4773457fbart trace_total = 1; 598f822af9b234e7c553c408eba65a641c4773457fbart break; 6072ab1ffbc336b17236e6f0b3f8e6919559de0de4bart default: 6172ab1ffbc336b17236e6f0b3f8e6919559de0de4bart fprintf(stderr, "Error: unknown option '%c'.\n", optchar); 6272ab1ffbc336b17236e6f0b3f8e6919559de0de4bart return 1; 6372ab1ffbc336b17236e6f0b3f8e6919559de0de4bart } 6472ab1ffbc336b17236e6f0b3f8e6919559de0de4bart } 6572ab1ffbc336b17236e6f0b3f8e6919559de0de4bart 6672ab1ffbc336b17236e6f0b3f8e6919559de0de4bart if (optind + 1 != argc) 6772ab1ffbc336b17236e6f0b3f8e6919559de0de4bart { 6872ab1ffbc336b17236e6f0b3f8e6919559de0de4bart fprintf(stderr, "Error: wrong number of arguments.\n"); 69cfe9672b7b0b64499c884109816bc543ce4f43cdbart return 1; 7072ab1ffbc336b17236e6f0b3f8e6919559de0de4bart } 7172ab1ffbc336b17236e6f0b3f8e6919559de0de4bart n = atoi(argv[optind]); 7272ab1ffbc336b17236e6f0b3f8e6919559de0de4bart 730aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart // Not the most user-friendly way to do error checking, but better than 740aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart // nothing. 750aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart assert(n > 2); 760aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart assert(num_threads >= 1); 770aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart 780aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart primes = malloc(n * sizeof(primes[0])); 790aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart pflag = malloc(n * sizeof(pflag[0])); 800aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart 810aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart omp_set_num_threads(num_threads); 820aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart omp_set_dynamic(0); 830aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart 840aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart for (i = 0; i < n; i++) { 850aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart pflag[i] = 1; 860aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart } 870aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart 888f822af9b234e7c553c408eba65a641c4773457fbart if (trace_total) 898f822af9b234e7c553c408eba65a641c4773457fbart DRD_TRACE_VAR(total); 908f822af9b234e7c553c408eba65a641c4773457fbart 910aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart#pragma omp parallel for 920aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart for (i = 2; i < n; i++) 930aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart { 940aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart if (is_prime(pflag, i)) 950aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart { 960aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart primes[total] = i; 970aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart total++; 980aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart } 990aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart } 10072ab1ffbc336b17236e6f0b3f8e6919559de0de4bart if (! silent) 1010aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart { 10272ab1ffbc336b17236e6f0b3f8e6919559de0de4bart printf("Number of prime numbers between 2 and %d: %d\n", 10372ab1ffbc336b17236e6f0b3f8e6919559de0de4bart n, total); 10472ab1ffbc336b17236e6f0b3f8e6919559de0de4bart for (i = 0; i < total; i++) 10572ab1ffbc336b17236e6f0b3f8e6919559de0de4bart { 10672ab1ffbc336b17236e6f0b3f8e6919559de0de4bart printf("%d\n", primes[i]); 10772ab1ffbc336b17236e6f0b3f8e6919559de0de4bart } 1080aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart } 1090aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart 1100aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart free(pflag); 1110aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart free(primes); 1120aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart 1130aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart return 0; 1140aeb186a549bd6cfc9d2e57c98f4ddca685c37f2bart} 115