对一个大于1的天然数 n 顺序确定 2 → √n 是否整除 n,即使创造一个数能整除 n,那么 n 不是素数,要不是。

C++代码如次:

bool isPrime(int n)

{

if (n <= 1)

return false;i

for (int i = 2; i * i < n; i++)

if (n % i == 0)

return false;

return true;

}

这种本领功夫搀杂度很高,咱们不妨借助数论常识进前进一步的优化。

素数散布顺序:当 n >= 5 时,即使 n 为素数,那么 n % 6 = 1 || n % 6 = 5,即 n 确定出此刻 6x(x ≥ 1)两侧。换句话说,大肆一个素数都不妨被表白为 6x ± 1 , x ϵ N 的情势。

表明:

把 6x 邻近的数用以次办法表白:

……(6x – 1), 6x, 6x+1, 2(3x+1), 3(2x+1), 2(3x +2), 6x + 5, 6(x+1)……

不在6x两侧的数为: 2(3x+1), 3(2x+1), 2(3x +2),它们不是素数,以是素数出此刻 6x 的两侧。

所以不妨获得以次优化:

bool isPrime(int n)

{

if (n <= 1)

return false;

if (n <= 3)

return true;

if (n % 2 == 0 || n % 3 == 0)

return false;

for (int i = 5; i * i < n; i += 6)

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

return false;

return true;

}

大略取余算法搀杂渡过高,故只符合于判决较小的数。