取余算法
对一个大于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; }
简单取余算法复杂度过高,故只适合于判定较小的数。