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。

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

有谁知道他是对的吗？如果是这样，对于多核架构，正确的做法是什么？

Answer 1

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