C-确定数字是否为质数

C-确定数字是否为质数

OK，所以就不用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。

bool

C中没有类型，no

true

或no

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（number）时停止检查。由于这

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

为负数，零或一，则此函数将声称该数字为质数。您可能希望适当地处理它，并且可能希望使其

number

不带符号，因为您更可能只关心正值：

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;}

这绝对不是检查数字是否为质数的最快方法，但是它可以工作，而且非常简单。我们几乎不需要修改您的代码！