| 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); |
| } |