C - 如果是素数,如何轻松测试？

Question

可能重复:
C - 确定数字是否为素数

有没有办法在C中轻松测试所选数字是否为素数？

Answer 1

最简单的方法是编写一个循环,如:

int is_prime(int num)
{
     if (num <= 1) return 0;
     if (num % 2 == 0 && num > 2) return 0;
     for(int i = 3; i < num / 2; i+= 2)
     {
         if (num % i == 0)
             return 0;
     }
     return 1;
}

然后,您可以优化它,迭代到floor(sqrt(num)).

Answer 2

最快的方法是预先计算您感兴趣的范围内所有可能整数的位数组（指示素数/非素数）。对于 32 位无符号整数，只有 512M，这很容易适合现代地址空间（并且，即使没有，这也会是一个快速的文件查找）。

这几乎肯定比每次通过筛子计算要快。