c - 高效素数函数

Question

所以我正在尝试创建一个函数，该函数将返回 1 或 0，具体取决于给定数字是否为质数。

注意：我确定给定的数字是自然的。大于 1

我原来的功能：

int Prime(int a) {
    int i;
    for (i = 2; i*i <= a; i++)
    {
       if ((a % i) == 0)
          return 0;
    };
    return 1;
}

工作得很好，但不知何故......慢。我正在寻找一种不使用数组的更有效的算法。我的第二次尝试：

int Prime(int a) {
    int i;
    if (a == 2)
       return 1;
    if ((a % 2) == 0)
       return 0;

    for (i = 3; i*i <= a; i = i + 3)
    {
       if ((a % i) == 0) 
          return 0;
    };

    return 1;
}

结局很糟糕。有一些数字（我无法真正想象）小于MAX_INT，这会导致这个特定算法的工作非常缓慢。所以，我有两个问题：

1. 我升级的算法有问题吗？

2. 有没有办法更有效地完成这项任务？

Answer 1

1）我升级的算法有问题吗？

是的。

i=i+3必须是i=i+2，否则您将检查 3 的倍数 (3,6,9,12,...) 而不是奇数 (3,5,7,9,...)

2）有什么方法可以更有效地完成这项任务？

您可以在开始时计算sqrt(a)并将其分配给变量（例如sqrtOfA），然后检查i <= sqrtOfA您的循环条件。

或者你可以试试像Eratosthenes筛子这样的素数筛子。

Answer 2

这取决于您是否想知道数字是素数还是仅具有高概率素数。如果您对程序可能给出错误答案或流星崩溃而感到满意，而流星崩溃的可能性更大，那么您可以使用像 Miller-Rabin 测试这样的 O(1) 检查。

http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

还有一个用于素数测试的确定性 O(n^12) 算法，但在实践中使用不多。

Answer 3

@Dukeling 是绝对正确的。另外，我想添加一个小条件来检查“是 1 素数吗？”

因为在标准程序中，在循环本身的帮助下，我们得到 1 不是素数。但是在这里，我们必须为此手动添加一个条件。

因此，只需添加以下“if”条件，您的代码就会完美运行！

if(a==1)
return 0;