algorithm - 数的素数

Question

众所周知，要检查数字“n”是否为素数，我们只需要检查它是否具有小于 n 平方根的因数。

我的问题是检查所有小于 n 平方根的素数是否足够。

Answer 1

每个大于 1 的整数n要么是素数本身，要么是素数的乘积（算术基本定理）。因此，如果n本身不是素数，则它必须能被至少两个素数整除。其中至少一个必须小于或等于√<em>n（否则它们的乘积将大于n），因此检查所有小于或等于√<em>n 的素数就足够了。

Answer 2

是的，只需要检查小于 sqrt(n) 的因子。但是这个算法有点慢。我还有一个更好的算法叫 Miller_Rabin_primality我之前的项目代码 源代码

这是维基

Answer 3

我们可以这样争论：

让要检查的数字是n。假设有一个k <= sqrt(n)除以的数n。现在，我们可以这样写k：

k = (p_1^a_1)(p_2^a_2)...(p_x^a_x)

其中p_1, p_2, ..., p_x是 小于或等于k和的素数a_1, a_2, ..., a_x >= 1。现在，既然k有n，又因为我们知道那个，我们可以通过及物性推导p_1, p_2, ..., p_x出那个。因此，要证明它是非素数，只需检查任何素数是否相除就足够了。kp_1, p_2, ..., p_xnn<= sqrt(n)n

Answer 4

是的，你说的完全正确。

您只需要检查所有小于等于 的素数squareRoot(n)，但关键是您不知道该数字是否为素数。所以，你遍历直到squareRoot(n)