c - 质数的多线程搜索

Question

我有这段代码正在计算输入数字下方的素数数量：

#include<stdio.h>
#include<Math.h>

int is_prime(long num)
{
    int k = 1, a = 0, b = 0;
    long sr;
    switch(num)
        {
        case 1: return 0;
        case 2: return 1;
        case 3: return 1;
        case 4: return 0;
        case 5: return 1;
        case 6: return 0;
        case 7: return 1;
    }
    if (num % 2 == 0) return 0;
    if (num % 3 == 0) return 0;
    sr = (int) sqrt(num);
    while (b < sr) {
        a = (6 * k) - 1;
        b = (6 * k) + 1;
        if (num % a == 0)
            return 0;
        if (num % b == 0)
            return 0;
        k += 1;
    }
    return 1;
}

void main()
{
    int j;
    long num=0;
    printf("insert your number to check for prime numbers\n");
    scanf("%ld",&num);
    for (j = 0; j<num; j++){
        if (is_prime(j))
            printf("%d is a prime\n", j);
    }
}

挑战的一部分——有人问我是否可以通过多核处理来加速我的计算，我回答是的。例如，如果我想检查 100 以下的素数，我将使用线程一来计算 2-50，使用线程二来计算 51-99。

他说我得考虑一下，因为在第一个核心上运行 2-50 和在第二个核心上运行 51-99 对于 x 等于 100 存在基本错误。

有人知道他是否正确吗？如果是这样，多核架构的正确方法是什么？

Answer 1

一般来说，计算 is_prime(n+k) 的工作量大于计算 is_prime(n) 的工作量。您将所有最简单的工作都交给了一个核心，而将所有最困难的工作交给了另一个核心，这意味着您不太可能接近理想的 2 倍速度，如果您将其分配得更均匀（例如，天真地，一个是偶数，另一个是奇数，所以工作量大致平均分配。除非不要那样做；我希望你能发现明显的缺陷，那里:)

Answer 2

我这样做的方式是这样的：

   void threadfunction()
   {
       for(;;)
       {
          number = pick_next_number();   // Should be atomic. 
          if (number > maxnumber)
              return;
          if (is_prime(number))
              printf("%d\n", number);
       }
   }

然后基本上只运行你需要的尽可能多的这些。

有几个问题是printf不是线程安全的，即使printf是线程安全的，它也可能会乱序输出数字。因此，您需要解决这些问题 - 例如，通过在数组中使用原子存储，并在执行结束时简单地打印它们。

Answer 3

您可以通过使用素数定理 π(x)~x/ln(x) 得到小于 N 的素数的非常接近的近似值

π(x) 是与 pi 常数无关的素数计数函数。