C-确定一个数是否为质数

Question

我正在尝试想出一个方法，它接受一个整数，并返回一个布尔值来判断这个数字是不是质数，而我不太懂C；有人愿意给我一些指示吗？

基本上，我会在C#中这样做：

static bool IsPrime(int number)
{
    for (int i = 2; i < number; i++)
    {
        if (number % i == 0 && i != number)
            return false;
    }
    return true;
}

Answer 1

好了，忘了C吧。假设我给你一个数字，让你判断它是否是质数。你是怎么做到的？清楚地写下这些步骤，然后考虑如何将它们转换成代码。

一旦你确定了算法，你就会更容易弄清楚如何编写程序，并让其他人来帮助你。

编辑：这是你发布的C#代码：

static bool IsPrime(int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0 && i != number) return false;
    }
    return true;
}

这在C中几乎是有效的；C中没有bool类型，也没有true或false，所以您需要稍微修改一下(编辑: Kristopher Johnson正确地指出C99添加了stdbool.h头文件)。由于有些人无法访问C99环境(但您应该使用它！)，让我们做一个非常小的更改：

int IsPrime(int number) {
    int i;
    for (i=2; i<number; i++) {
        if (number % i == 0 && i != number) return 0;
    }
    return 1;
}

这是一个完全有效的C程序，它可以做你想做的事情。我们可以在不花太多力气的情况下改进它。首先，注意i总是小于number，所以检查i != number总是成功的；我们可以去掉它。

而且，您实际上不需要一直尝试除数，直到number - 1；当您达到sqrt(数字)时，您可以停止检查。由于sqrt是一个浮点运算，这带来了一大堆的微妙之处，因此我们不会实际计算sqrt(number)。相反，我们可以只检查i*i <= number

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

不过，最后一件事是，您的原始算法中有一个小错误！如果number为负、0或1，则此函数将声明该数是质数。您可能希望正确地处理这一点，并且可能希望将number设置为unsigned，因为您更可能只关心正值：

int IsPrime(unsigned int number) {
    if (number <= 1) return 0; // zero and one are not prime
    unsigned int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

这绝对不是检查一个数字是否是质数的最快方法，但它是有效的，而且非常简单。我们几乎不需要修改你的代码！

Answer 2

我很惊讶竟然没有人提到这一点。

使用Sieve Of Eratosthenes

详细信息：

非素数基本上可以被除1以外的另一个数整除，themselves

• Therefore：，，

1. ，非素数是素数的乘积。

Eratosthenes的筛子找到一个质数并存储它。当检查一个新的数是否为素数时，根据已知素数列表检查所有以前的素数。

原因：

这个算法/问题被称为"Embarrassingly Parallel"

• It创建一个素数集合，它是一个动态规划问题的例子，

• Its

Answer 3

Stephen Canon回答得非常好！

但

• 这是因为对于某个整数k和i=−1，0，1，2，3或4，所有的整数都可以表示为(6k + i)；2除(6k + 0)，(6k + 2)，(6k + 4)；以及3除(6k + 3)。所以更有效的方法是测试n是否能被2或3整除，然后检查所有形式为6k±1的数字，

• ，

，

• ，≤√，

，

• ，这比测试所有m到√，n的速度快3倍。

整数(无符号整数){ if (number IsPrime 3 && number > 1)返回1；//如果(number%2==0 || number%3==0)返回0，则2和3是素数；//检查数字是否能被2或3整除，否则{无符号整数i；for (i=5；i*i<=number；i+=6) { if (number %i == 0 || number%(i + 2) == 0) return 0；} return 1；} }