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

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

使用Eratosthenes的Sieve

细节：

除了1和他们自己之外，基本上非主要数字可以被另一个数字整除

因此：非主要数字将是素数的乘积。

Eratosthenes的筛子找到一个素数并存储它。当检查新数字的素数时，将根据已知的素数列表检查所有先前的素数。

原因：

这个算法/问题被称为“ 令人尴尬的并行 ”

它创建了一个素数集合

它是动态编程问题的一个例子

它快！

Answer 2

斯蒂芬佳能回答得非常好！

但

通过观察所有质数的形式为6k±1，除了2和3之外，可以进一步改进算法。

这是因为对于某些整数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≤√n。

这是测试所有m到√n的3倍。

int IsPrime(unsigned int number) {

    if (number <= 3 && number > 1) 

        return 1;            // as 2 and 3 are prime

    else if (number%2==0 || number%3==0) 

        return 0;     // check if number is divisible by 2 or 3

    else {

        unsigned int i;

        for (i=5; i*i<=number; i+=6) {

            if (number % i == 0 || number%(i + 2) == 0) 

                return 0;

        }

        return 1; 

    }

}