Check Prime Number
质数是大于 1 的整数，它的因数只有 1 和它本身。给你一个正整数 n。如果 n 是质数，返回 true，否则返回 false。数字 1 不是质数。
函数
- ninteger
- 要测试的正整数
- 返回值boolean
- 如果 n 是素数，则为 true，否则为 false。
约束条件
1 ≤ n ≤ 231 - 1
示例
- 输入
- n = 29
- 输出
- true
- 解释
2、3、4和5都不能整除29，而6 × 6 = 36已经超过了29，所以没有剩下的因数需要寻找。29是质数。
- 输入
- n = 1
- 输出
- false
- 解释
- 质数恰好有两个因数：
1和它本身。1只有一个因数，所以答案是false。
- 输入
- n = 91
- 输出
- false
- 解释
91看起来是质数，但7 × 13 = 91。在搜索范围超过√91 ≈ 9.5之前，就会找到除数7。
进阶
所有大于 3 的素数都可以写成 6k-1 或 6k+1 的形式。你能利用这一点，只测试三分之一的候选除数吗？
提示
逐个打开提示，每个都会多透露一点。
质数在
2和n-1之间没有任何因数。你真的需要测试整个范围吗？如果
d能整除n，那么n / d也能整除n，并且这两个数中至少有一个不大于√n。当d * d大于n时，你就可以停止了。先排除
n < 2和除2以外的偶数。然后从3开始测试奇数除数，直到d * d ≤ n，并确保d * d使用 64 位类型。
题解
对于最大的素数输入，测试从 2 到 n-1 的每个除数需要进行超过 20 亿次除法。除数会成对出现，每对相乘等于 n，且每对中较小的除数最多为 √n。因此，你只需搜索到 √n：最多约有 23,000 个奇数候选值。
尝试每一个除数
结果正确，但无法在最大的测试中运行完毕
思路
用 d 从 2 到 n-1 逐个测试候选值，检查 n % d == 0，并在第一个能整除 n 的值处返回 false。这就是素数的定义，因此只要在 n < 2 时返回 false，这个方法就是正确的。
素数能通过每一次测试，因此循环会一直运行到结束。对于素数 n = 2147483647，这大约需要进行 2.1 × 10^9 次除法。
算法
- 如果
n < 2，返回false。 - 让
d从2循环到n-1。 - 如果
n % d == 0，返回false。 - 循环结束后，返回
true。
def isPrime(n):
if n < 2:
return False
for d in range(2, n):
if n % d == 0:
return False
return True试除法至平方根
思路
如果 d 能整除 n，那么 n / d 也能整除 n。这两个数不可能都大于 √n，否则它们的乘积就会大于 n。因此，合数 n 总有一个不大于 √n 的因数：对于 91，这对因数是 7 和 13，且 7 ≤ 9.5。如果没有小于或等于 √n 的数能整除 n，那么 n 就是素数。
将边界条件写成 d * d ≤ n，这样只用整数计算，无需四舍五入。单独处理 2，因为偶数 n 只有在等于 2 时才是素数。奇数 n 只有奇数因数，所以从 3 开始，每次递增 2。对于 n = 2147483647，循环大约运行 23,000 次。
算法
- 如果
n < 2，返回false。 - 如果
n是偶数，返回n == 2的结果。 - 将
d设为3，并在d * d ≤ n时循环，使用 64 位类型表示d。 - 如果
n % d == 0，返回false。否则，将2加到d上。 - 循环结束后，返回
true。
def isPrime(n):
if n < 2:
return False
if n % 2 == 0:
return n == 2 # 2 is the only even prime
d = 3
while d * d <= n:
if n % d == 0:
return False
d += 2
return True
易错点和边界情况
- 对
1返回true。它只有一个因数，不是两个，因此它不是质数。 - 因为
2是偶数而拒绝它。排除偶数之前，先检查n == 2。 - 循环条件使用
d * d < n，而不是≤。这样一来，9和49这样的质数平方就会被当作质数。 d * d溢出。在 32 位的int中，46341 × 46341会变成负数，因此循环会远远超过√n。为d使用 64 位类型，或者比较d ≤ n / d。
常见问题3
检查一个数是否为质数的时间复杂度是多少？
试除法最多检查到 √n，耗时为 O(√n)，空间复杂度为 O(1)。当 n 最大为 2^31-1 时，最多约需进行 46,000 次除法；跳过偶数除数时，则约需 23,000 次。
1 是质数吗？
不是。质数恰好有两个不同的因数：1 和它本身，而 1 只有一个因数。不把 1 算在内，可以确保每个整数的质因数分解都是唯一的。
有没有更快的方法来测试非常大的数是否为质数？
对于一个 32 位数，试除法只需检查到 √n，速度就足够快。对于有几十位的数，程序会使用 Miller-Rabin 测试，它会检查几个模幂，而不是尝试除数。要列出不超过某个上限的所有质数，使用埃拉托斯特尼筛法比逐个测试每个数更高效。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isPrime(n):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
n = 29
预期输出
true