1. 质数判断算法解析
质数判断是编程中常见的基础算法问题,也是检验程序员基本功的经典题目。我们先来理解质数的数学定义:质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的数。换句话说,质数只能被1和它自身整除。
1.1 基础判断方法
最直观的判断方法是试除法:对于一个给定的数n,我们从2开始,一直试除到n-1,如果都不能整除,则n是质数。这种方法虽然简单直接,但效率很低,时间复杂度为O(n)。
cpp复制bool isPrime_naive(int n) {
if (n <= 1) return false;
for (int i = 2; i < n; i++) {
if (n % i == 0) return false;
}
return true;
}
1.2 优化思路:平方根边界
数学上可以证明,如果n不是质数,那么它一定有一个因数小于等于√n。因此,我们只需要检查2到√n之间的数即可,这样时间复杂度降为O(√n)。
cpp复制bool isPrime_sqrt(int n) {
if (n <= 1) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
注意:这里使用i*i <= n而不是i <= sqrt(n)是为了避免重复计算平方根,提高效率。这种写法是C++中常见的优化技巧。
1.3 进一步优化:排除偶数
除了2以外,所有偶数都不是质数。我们可以先排除偶数,然后只检查奇数,这样循环次数减少一半。
cpp复制bool isPrime_optimized(int n) {
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0) return false;
}
