c - C语言中的素数

Question

我想通过多线程和使用E.函数的Sieve来查找素数。我写了一些代码。如果程序将运行，用户输入最大数量和线程数量。程序应该创建给定线程号的线程。该程序找到所有素数，直到最大数。每个线程必须检查一个素数。

我的程序找不到素数。我编写了 checkPrime 函数和 crossout 函数来有效地查找素数。但这不起作用。所以，我无法检查我的线程是否正常工作。如何实现checkPrime功能？

有3个功能。划线用于 Sieve E. 方法。 checkPrime 用于检查数字是否为质数。 worker是线程的功能。每个线程必须检查一个质数。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <pthread.h>

#define MAX_N 100000000
#define MAX_THREADS 25

// global values
int threadNumber;
int largestNumber;
int isPrime;
int nthreads,  // number of threads (not counting main())
    prime[MAX_N + 1],
    n,  // in the end, prime[i] = 1 if i prime, else 0
    nextbase;  // next sieve multiplier to be used

// lock for the shared variable nextbase
pthread_mutex_t nextbaselock = PTHREAD_MUTEX_INITIALIZER;

void crossout(int a) {
    int i, j, check;
    for (i = 2; i < largestNumber; i++)
        prime[i] = 1;

    for (i = a; i < largestNumber;)
        if (prime[i])
            for (j = i; i * j < largestNumber; j++)
                prime[i * j] = 0;

}

int checkPrime(int a) {
    int i;
    for (i = 2; i <= a; ++i) {
        if (a % i == 0) {
            isPrime = 1;
            return isPrime;
            break;
        } else
            isPrime = 2;
        crossout(a);
        return isPrime;
    }
}

void*  workerThread(void* t) {

    int lim, base;

    long i, j;
    long tid;

    tid = (long)t;
    printf("Thread %ld starting...\n", tid);

    while (1)  {


        pthread_mutex_lock(&nextbaselock);
        base = nextbase;
        nextbase++;
        // unlock the lock
        pthread_mutex_unlock(&nextbaselock);
        if (base <= lim)  {

            if (prime[base])  {
                checkPrime(base);
                // log work done by this thread
            }
        }
        if (checkPrime(base) == 2)
            printf("Thread %ld done. Prime = %d\n", tid, base);
        pthread_exit((void*) t);
    }

    return NULL;
}

//main function with two parameters :argc and argv
int main(int argc, char** argv) {

    threadNumber = argv[3];
    largestNumber = argv[1];


    int i;

    pthread_t thread[threadNumber];
    int rc;
    long t;
    void* status;

    for (t = 0; t < threadNumber; t++) {
        printf("Main: creating thread %ld\n", t);
        rc = pthread_create(&thread[t], NULL, workerThread, (void*)t);
        if (rc) {
            printf("ERROR; return code from pthread_create() is %d\n", rc);
            exit(-1);
        }
    }

    for (t = 0; t < threadNumber; t++) {
        rc = pthread_join(thread[t], (void*)&t);
        if (rc) {
            printf("ERROR; return code from pthread_join() is %d\n", rc);
            exit(-1);
        }
        printf("Main: completed join with thread %ld \n", t);
    }
}

Answer 1

您正在尝试混合两种不同的方法来查找素数。您不需要同时使用迭代除法和埃拉托色尼筛法。这显示了一种实现筛子的方法。偶数在筛子中会被忽略，但在 isprime() 中被视为特殊情况。但它不会帮助您找到多线程解决方案，因为您不能只是将不同的数字交给不同的线程 - 每个素数都建立在前一个素数的工作基础上，从假设 3 是质数。

// Sieve of Eratosthenes
#include <stdio.h>
#include <stdlib.h>

#define LIMIT   200

char sieve[LIMIT] = { 1, 1, };                  // 1 for not-prime

int isprime(unsigned n)
{
    if(n <= 2)                                  // special cases
        return sieve[n] == 0;
    if(n % 2 == 0)                              // even numbers are not prime
        return 0;
    if(n >= LIMIT)                              // test range
        exit(1);
    return sieve[n] == 0;
}

int main(void)
{
    unsigned n, p;
    for(n=3; n<LIMIT; n+=2) {                   // odd numbers only
        if (sieve[n] == 0) {                    // if n is prime
            for(p=n*n; p<LIMIT; p+=n*2) {       // ignore even numbers
                sieve[p] = 1;                   // not primne
            }
        }
    }

    printf("Prime numbers are:\n");
    for(n=0; n<LIMIT; n++) {                    // check all numbers
        if (isprime(n)) {                       // if n is prime
            printf("%-4d", n);
        }
    }
    printf("\n");
    return 0;
}

程序输出:

Prime numbers are:
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  101 103 107 109 113 127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199

我现在将展示一种迭代除法。偶数再次被视为特殊情况。我不经常编写多线程 C 代码，所以我无法帮助你。但我希望您可以在第二个示例的基础上构建多线程解决方案。

// iterative division
#include <stdio.h>
#include <math.h>

#define LIMIT   200

int isprime(unsigned n)
{
    unsigned s, i;
    if(n <= 1)
        return 0;
    if(n == 2)
        return 1;
    if(n % 2 == 0)                              // no even numbers
        return 0;
    s = (unsigned)sqrt(n);                      // limit the loop
    for(i=3; i<=s; i+=2)                        // odd numbers only
        if (n % i == 0)
            return 0;
    return 1;
    }

int main(void)
{
    unsigned n;
    printf("Prime numbers are:\n");
    for(n=0; n<LIMIT; n++) {                    // check all numbers
        if (isprime(n)) {                       // if n is prime
            printf("%-4d", n);
        }
    }
    printf("\n");
    return 0;
}

程序输出:

Prime numbers are:
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  101 103 107 109 113 127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199

在处理较大数字时，上述两个示例都存在一些陷阱，但我将把它们留给您去发现。