答案是判断质数需检查2到√n的因数。若n大于1且无小于等于√n的因数，则为质数，如代码所示，时间复杂度优化至O(√n)。
判断一个数是否是质数在C++中是一个常见的编程问题。质数是指大于1且只能被1和它本身整除的自然数。例如：2、3、5、7、11等。
要判断一个整数n是否为质数，最直接的方法是尝试用从2到n-1的所有数去除n，如果存在能整除的数，则n不是质数。但这种方法效率较低，可以进行优化。
只需检查从2到√n之间的所有整数即可。因为如果n有一个大于√n的因数，那么必然有一个小于√n的对应因数。
示例代码：
#include <iostream><br>#include <cmath><br>using namespace std;<br><br>bool isPrime(int n) {<br> if (n <= 1) return false; // 小于等于1的数不是质数<br> if (n == 2) return true; // 2是质数<br> if (n % 2 == 0) return false; // 偶数（除了2）不是质数<br><br> int limit = sqrt(n);<br> for (int i = 3; i <= limit; i += 2) {<br> if (n % i == 0)<br> return false;<br> }<br> return true;<br>}<br><br>int main() {<br> int num;<br> cout << "请输入一个整数：";<br> cin >> num;<br><br> if (isPrime(num))<br> cout << num << " 是质数。" << endl;<br> else<br> cout << num << " 不是质数。" << endl;<br><br> return 0;<br>}
基本上就这些。这个方法对于一般用途已经足够高效，适用于大多数场景下的质数判断。
立即学习“C++免费学习笔记（深入）”；
c++怎么学习？c++怎么入门？c++在哪学？c++怎么学才快？不用担心，这里为大家提供了c++速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！
广告Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
521
收藏
