この素数ジェネレーターの c コードを確認できます。
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#define NUMITERS 200
#define MAXSIZE 500000
#define MAXNUMPROCS 64
#define PRIME(num) (2*(num) + 3)
#define NUM(prime) (((prime) - 3)/2)
#define TRUE 1
#define FALSE 0
int lastPrime, count; /* Last Prime and Number of Primes Found */
int size = 1000; /* Number of numbers to test for prime */
int numProcs = 1; /* Number of processors */
FILE *out = NULL; /* File to output primes to */
char *flags; /* Array of primes (odd numbers only)
i.e. flags[0] corresponds to 3
flags[1] corresponds to 5
flags[n] corresponds to 2*n+3
flags[i] is TRUE if i is a prime */
void primes(void); /* procedure prototype */
void parallelPrimes(void); /* procedure prototype */
/**
* prints the usage instructions and exits
*/
void usage(char *filename) {
printf("Usage: %s <flags>\n", filename);
printf("\t-m <num>\tMaximum number to test\n");
printf("\t-p <num>\tNumber of processors being run on\n");
printf("\t-o <filename>\tFilename to output primes to\n");
printf("\t-s\t\tOutput primes to stdout\n");
printf("\t-h\t\tDisplay these usage instructions\n");
exit(0);
}
/**
* main routine:
*
*/
int main(int argc, char *argv[])
{
int i;
int opt;
do {
char *test;
opt = getopt(argc, argv, "p:m:o:sh");
switch (opt) {
case 'p':
numProcs = atoi(optarg);
if (numProcs < 1 || numProcs > MAXNUMPROCS) {
printf("Invalid number of processors -- %d\n\n", numProcs);
usage(argv[0]);
}
break;
/* set maximum number to test */
case 'm':
size = NUM(atoi(optarg));
if (size < 0 || size > MAXSIZE) {
printf("Invalid maximum number to test -- %d\n\n", size);
usage(argv[0]);
}
break;
/* select outputing the primes to stdout */
case 's':
if (out != NULL) {
printf("multiple output locations is unsupported\n\n");
usage(argv[0]);
}
out = stdout;
break;
/* set the file to output the primes to */
case 'o':
if (out != NULL) {
printf("multiple output locations is unsupported\n\n");
usage(argv[0]);
}
out = fopen(optarg, "w");
if (out == NULL) {
printf("Unable to open \"%s\"\n\n", optarg);
usage(argv[0]);
}
break;
/* help */
case 'h':
usage(argv[0]);
break;
/* unknown argument */
case '?':
usage(argv[0]);
break;
/* -1, we're done */
default:
break;
}
} while(opt > 0);
if (optind < argc) {
printf("Unknown argument -- %s\n\n", argv[optind]);
usage(argv[0]);
}
printf(" Prime Generator (testing %d numbers, %d iterations on %d procs)\n",
size, NUMITERS, numProcs);
flags = (char *) malloc(size * sizeof( char ) );
if (!flags) {
printf("\n Could Not Allocate Memory for Array Size: %d\n",size);
exit(1);
}
if (numProcs == 1)
primes(); /* Call our primes routine */
else
parallelPrimes();
/* print out all of the primes found */
if (out != NULL) {
int i;
fprintf(out, "2\n");
for (i = 0; i < size; ++i)
if (flags[i])
fprintf(out, "%d\n", PRIME(i));
}
free(flags);
printf(" Number of primes = %d, largest prime = %d\n", count, lastPrime);
}
/**
* primes: single-threaded prime number searching routine.
*
* We test each odd number n to see if it's prime by dividing
* by all smaller primes <= sqrt(n) and checking to see if the remainer
* is zero.
*/
void primes()
{
int i;
int iter, prime;
int div1, div2, rem;
for (iter=0; iter < NUMITERS; ++iter)
{
count = 0;
lastPrime = 0;
for (i=0; i < size; ++i) { /* For every odd number */
prime = PRIME(i);
/* Keep searching for divisor until rem == 0 (i.e. non prime),
or we've reached the sqrt of prime (when div1 > div2) */
div1=1;
do {
div1 += 2; /* Divide by 3, 5, 7, ... */
div2 = prime / div1; /* Find the dividend */
rem = prime % div1; /* Find remainder */
} while (rem != 0 && div1 <= div2);
if (rem != 0 || div1 == prime) {
/* prime is really a prime */
flags[i] = TRUE;
count++;
lastPrime = prime;
} else {
/* prime is not a prime */
flags[i] = FALSE;
}
}
}
}
/**
* parallelPrimes: multi-threaded prime number searching routine.
*
* We test each odd number n to see if it's prime by dividing
* by all smaller primes <= sqrt(n) and checking to see if the remainer
* is zero.
*/
void parallelPrimes()
{
// TODO: Parallelize this function
// You may find the numProcs global variable to be useful here
int i;
int iter, prime;
int div1, div2, rem;
for (iter=0; iter < NUMITERS; ++iter)
/* This is just to make running time reasonable.
Don't parallelize this loop */
{
count = 0;
lastPrime = 0;
for (i=0; i < size; ++i) { /* For every odd number */
prime = PRIME(i);
/* Keep searching for divisor until rem == 0 (i.e. non prime),
or we've reached the sqrt of prime (when div1 > div2) */
div1=1;
do {
div1 += 2; /* Divide by 3, 5, 7, ... */
div2 = prime / div1; /* Find the dividend */
rem = prime % div1; /* Find remainder */
} while (rem != 0 && div1 <= div2);
if (rem != 0 || div1 == prime) {
/* prime is really a prime */
flags[i] = TRUE;
count++;
lastPrime = prime;
} else {
/* prime is not a prime */
flags[i] = FALSE;
}
}
}
}