DAPPLE Example: prime

Source code:

// prime -- a parallel prime-number program // written using the Data-Parallel Programming Library for Education (DAPPLE) // // This program uses the Sieve of Erasthenes to produce prime numbers. // It produces one prime number in each iteration, and then divides // all candidate numbers by that prime in parallel, to reduce the set of // candidates. // This algorithm is not very efficient, because even after a number is // determined to be composite, it still occupies a virtual processor and // still participates in the computation. // // David Kotz 1994 // $Id: prime.cc,v 2.13 94/09/29 12:18:28 dfk Exp $ #include #include #include #include "dapple.h" const int N = 100; const intVector VP(N, Identity); // which VP am I? int main(int argc, char **argv) { booleanVector candidate(N); // VP i is a candidate if candidate[i] true int prime; // a prime number // each VP represents one of the possible numbers 0..N-1 // those where candidate==true are possible prime numbers // initially, all >= 2 are considered possible prime numbers candidate = (VP >= 2); // true except for VPs 0 and 1 // repeatedly, // note that the first VP with candidate==true is a prime number // print that prime out // set candidate=false for all VPs whose index is divisible by prime // stop when there are no remaining candidates. while (any(candidate)) { ifp (candidate) prime = first(VP); // first number is a prime cout << prime << endl; // print that prime number ifp (VP % prime == 0) // all those VPs divisible by this prime candidate = false; // drop out from consideration } return(0); }

Demonstration:

prime 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97