时间戳

首页 > 解决方案 > 使用 C 中的多线程进行长数素数检测

c - 使用 C 中的多线程进行长数素数检测

问题描述

问题陈述：检测一个长整数是否是素数。
我的逻辑：
这个想法是从 0 迭代到 sqrt(n)。如果在 0 到 sqrt(n) 之间没有找到除数，那么我可以得出结论，该数字是素数，否则是非素数。
因为，这需要多线程，所以我创建了一个名为void* PrimeDetecter(void* param);. 在这个线程函数中，我将从startIndexto迭代endIndex，如果有一个除数，则退出线程并将值 1 写入到isNum1Prime默认设置为 0 的变量地址中的状态为真。
因此，在主函数中，我需要在创建线程时将要检查的数字、开始索引和结束索引发送给线程。所以我的结构将包含long int number, startIndex, endIndex, *divisorand int isPrime。
然后我创建一个大小为 10 的 NumberPrime 类型的数组，因为有 10 个线程，因此将迭代平均划分。

我打印了线程之间的索引分布，效果很好。然后我只是创建线程并将所有这些元素发送到线程以检查数字是否为素数。
这是我的代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <math.h>
#include <pthread.h>

#define MAX_NUM_THREADS 10 // Exercise 1: Not more than 10 threads can run at a time for example.

struct NumberPrime
{
    long int number, startIndex, endIndex, *divisor;
    int *isPrime;
};

void *PrimeDetector(void *param)
{
    struct NumberPrime parameters = *(struct NumberPrime *)param;
    for (long int i = parameters.startIndex; i < parameters.endIndex; i++)
    {
        if (i == 0 || i == 1)
        {
            break;
        }
        else
        {
            if ((parameters.number % i) == 0) // if the divisor is detected then number is not a prime
            {
                *(parameters.divisor) = i;
                *(parameters.isPrime) = 1; // change the value to true
                pthread_exit(0);          // exit the thread function
            }
        }
    }
}

int main(int argc, char *argv[])
{
    long int number1 = 12340000, number2 = 128;
    struct NumberPrime primeData1[MAX_NUM_THREADS];
    int isNum1Prime = 0; // false
    long int number1Divisor = 0;
    long int numberSquareRoot1 = (long int)(sqrt(number1)); // get the square root of number1

    for (int i = 0; i < MAX_NUM_THREADS; i++)
    {
        primeData1[i].number = number1;
        primeData1[i].isPrime = &isNum1Prime;
        primeData1[i].divisor = &number1Divisor;
        primeData1[i].startIndex = i * numberSquareRoot1 / MAX_NUM_THREADS;
        primeData1[i].endIndex = ((i + 1) * numberSquareRoot1) / MAX_NUM_THREADS;
    }

    pthread_t primeDetectorThread1[MAX_NUM_THREADS];
    int count = 0;
    for (int i = 0; i < MAX_NUM_THREADS; i++)
    {
        if (isNum1Prime == 1)
        {
            pthread_cancel(primeDetectorThread1[i]);
            break;
        }
        else
        {
            pthread_create(&primeDetectorThread1[i], NULL, &PrimeDetector, &primeData1[i]);
            count++;
        }
    }
    for (int i = 0; i < count; i++)
    {
        pthread_join(primeDetectorThread1[i], NULL);
    }

    isNum1Prime == 1 ? printf("Number 1 is prime.\n") : printf("Number 1 is not prime and divisible by %ld\n", number1Divisor);
    return EXIT_SUCCESS;
}

预期的输出是该数字不是素数。但无论我选择什么数字，我总是认为这个数字是素数。

标签： cmultithreadinggccc99

解决方案

该行if ((parameters.number % i) == 0)测试一个数字是否能被 整除i。如果它是可整除的，则该数字不是素数，但您的代码会继续设置*(parameters.isPrime) = 1;和结束线程。

推荐阅读