埃拉托色尼筛法多线程找素数

beyes

埃拉托色尼筛法
利用埃拉托色尼筛法寻找 2~n 之间的素数，方法是去掉所有 2 的倍数，再去掉所有 3 的倍数，以此类推，最后剩下的就是素数。

下面程序使用多线程来完成：

include <stdio.h>

#include <math.h>

#include <pthread.h>

#define MAX_N           100000000

#define MAX_THREADS     100

int nthreads, n, prime[MAX_N + 1], nextbase;

int work[MAX_THREADS];

pthread_mutex_t nextbaselock = PTHREAD_MUTEX_INITIALIZER;

pthread_t id[MAX_THREADS];

void crossout (int k)

{

int i;

for (i = k; i*k <= n; i++) {    //最小为该数的平方,然后是依次向上为该数的倍数(3*3,3*4,3*5...)

prime[i*k] = 0;

}

}

void *worker (void *unuse)

{

int lim, base;

lim = sqrt(n);  //最大值的平方根为最大基数

do {

pthread_mutex_lock (&nextbaselock);

base = nextbase += 2;           //每个线程都有自己的局部变量,但nextbase是全局变量,会被所有线程共享,所以此处需要互斥锁保护

pthread_mutex_unlock (&nextbaselock);

if (base <= lim) {

if (prime[base])

crossout(base);

} else return;

} while (1);

}

int main (int argc, char **argv)

{

int nprimes, i;

if (argc != 3) {

printf ("usage: %s threads range ", argv[0]);

return (-1);

}

n = atoi (argv[1]);

if (n >= MAX_N) {

printf ("out of range ");

return (-1);

}

nthreads = atoi (argv[2]);

if (nthreads > 100) {

printf ("out of range ");

return (-1);

}

for (i = 2; i <= n; i++) //将所有数填充到数组

prime[i] = i;

crossout(2);    //2为素数,其余倍数不为素数

nextbase = 1;

for (i = 0; i < nthreads; i++) {

pthread_create (&id[i], NULL, (void *)worker, NULL);

}

for (i = 0; i < nthreads; i++) {

pthread_join (id[i], NULL);

}

for (i = 0; i < n; i++) {

if (prime[i] != 0)

printf ("%d  ", prime[i]);

}

printf (" ");

return (0);

}

编译：

gcc -g debug_pthread.c -lpthread -lm -o debug_pthread

运行与输出：

debug_pthread 100 5

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

用 5 个线程求 100 内的所有素数。