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) {&nbsp; &nbsp; if (number <= 3 && number > 1)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // as 2 and 3 are prime&nbsp; &nbsp; else if (number%2==0 || number%3==0)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; return 0;&nbsp; &nbsp; &nbsp;// check if number is divisible by 2 or 3&nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; unsigned int i;&nbsp; &nbsp; &nbsp; &nbsp; for (i=5; i*i<=number; i+=6) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (number % i == 0 || number%(i + 2) == 0)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return 0;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp;&nbsp; &nbsp; }}