c - 如何改进以下检查数字是否为素数的程序的 C 实现？

Question

作为编程练习，我尝试编写一个利用线程的程序，以便更快地计算一个数字是否为素数。 我的想法是 segmentation P 间隔中的数字，其中 P 作为命令行上的参数传递，然后评估每个线程内的间隔。 这里的问题是我必须评估区间内的每个奇数，这需要很多时间。

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


int prime = 1; // flag for detecting non-prime numbers
            // numbers are prime until a divisor is found

struct args {
   long long start; // start of the subset of the interval
   long long end; // end of the subset of the interval
   long long N; // input number
};

void * runner (void *arg); 
struct args * allocate_struct ( int P );
pthread_t * allocate_tids ( int P );

int 
main (int argc, char *argv[])
{
    int P; // number of threads
    long long N; // number to check
    pthread_t *tids;
    struct args *args_array;
    long long q; // quotient
    int i;

    if (argc != 3)
    {
        fprintf (stderr, "Wrong number of arguments\n");
        printf ("Correct usage: %s <input number> <number of threads to use>\n", argv[0]);
        exit(1);
    }

    N = atol(argv[1]); // fetch the input number

    if (N <=0)
    {
        fprintf (stderr, "The input number must be positive\n");
        exit(1);
    }

    P = atoi(argv[2]); //fetch the number of threads

    if (P <=0)
    {
        fprintf (stderr, "The number of threads must be positive\n");
        exit(1);
    }

    if (P > N) 
    {
        fprintf (stderr, "The number of threads must be smaller than the input number\n");
        exit(1);
    }

    q = (N/2)/(long long)P; // find the width of the intervals

    args_array = allocate_struct ( P );
    tids = allocate_tids ( P );

    /* the following instructions are used to define the sub-intervals among the P threads */
    args_array[0].start = 2;
    args_array[0].end = args_array[0].start+q;
    args_array[0].N = N;


for (i = 1; i < P; i += 1)
{
        args_array[i].start = args_array[i-1].end+1;
        args_array[i].end = args_array[i].start+q;
        args_array[i].N = N;
}

    /* threads are created and start running */
    for (i = 0; i < P; i += 1)
    {
        if (pthread_create(&tids[i], NULL, runner, (void *) &args_array[i]))
        {
            fprintf (stderr, "Error during creation of a thread\n");
            exit(1);
        }   
    }

    /* the main thread waits the end of the runner threads */
    for (i = 0; i < P; i += 1)
    {
        pthread_join(tids[i], NULL);
    }

    if (prime == 1)
    {
        printf("The number is prime.\n");
    } else {
        printf ("The number isn't prime.\n");
    }

    return 0;
}

void * runner (void * arg) {
    struct args * args;
    long long i;
    args = (struct args *) arg;
for (i = args->start; i < args->end && prime != 0; i += 1) // 
{
    if ((args->N % i) == 0 && (args->N != i))
        {
            prime = 0;
            printf("%lld is a divisor\n", i);
            pthread_exit(NULL);
        }
    }

    pthread_exit(NULL);
}

pthread_t * allocate_tids ( int P ){
    pthread_t *np_t;

    np_t = (pthread_t *) malloc (sizeof (pthread_t ) * P);

    if (np_t == NULL)
    {
        fprintf (stderr, "Error in allocation\n");
        exit(1);
    }

    return np_t;
}

struct args * allocate_struct ( int P ) {
    struct args *np_s;

    np_s = (struct args *) malloc (sizeof (struct args) * P);

    if (np_s == NULL)
    {
        fprintf (stderr, "Error in allocation\n");
        exit(1);
    }

    return np_s;
}

正如我所说，结果非常糟糕。我回到了单线程的想法并提出了以下想法:

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

int main (int argc, char ** argv) {
long long number;
long long i;
int prime = 1;

number = atol(argv[1]); 

if (number < 1) {
    printf("The number must be positive.\n");
    exit(1);
}

if (number == 2) 
{   
    prime = 1;
    i = 2;
}

else if (number == 3)
{ 
    i = 3;
    prime = 1;
}
else if (number % 2 == 0)
{
    i = 2;
    prime = 0;
}
else
{
    for ( i = 3; i <= number/i; i+=2 ) {
        if  (number%i == 0) { 
            prime = 0;
            break;
        } 
    }
}

if (prime) {
    printf("The number %lld is prime.\n", number);
} else {
    printf("The number %lld is not prime, its first divisor is %lld\n", number, i);
}

printf("Loop ended at iteration %lld\n", i);

return 0;

}

修复第一个程序中存在的所有问题后，它可以工作，并且需要大约 10 秒(1 个线程)/5 秒(4 个线程)来检查与下面的相同的数字(需要数十毫秒)。

好奇，我可以进一步改进第二个解决方案吗？怎么办？

另外，我对线程的经验不是很丰富，所以我可能在创建和使用方面犯了错误，请指出。

Answer 1

如果你检查一个数是否是素数，你通常很快就会发现它是合数，因为它的除数很小。除 48/210 之外的所有整数都可以被 2、3、5 或 7 整除。因此，为了获得良好的结果，一旦第一个线程(通常很快)找到了某个值，您就必须找到一种方法来阻止所有这些线程浪费 CPU 时间。除数。

或者，您可以首先测试直到 sqrt (x)/5 的所有除数，然后确定不太可能存在除数，并将范围的其余部分划分为四个线程。估计找到除数的机会并估计浪费了多少时间将是一个非常有趣的数学问题。

实际上，您可能想要检查许多 个数字的素数，并且您可以轻松地让一个线程检查一个数字。更容易、更高效地完成任务。