两种C++质数判断代码差异及sqrt优化逻辑必要性咨询

首先你的第一版代码存在致命逻辑错误 #

你写的第一版代码并不能正确判断质数，问题出在循环的分支逻辑：

#include <iostream>
#include<cmath>
using namespace std;

int main()
{
   int n;
   cout << "Enter the no. and we will tell you whether it's Prime or Non-Prime \n";
   cin >> n;
   
   for (int i=2; i<n; i++) {
       if (n%i== 0){
           cout << "Non-Prime"<< endl;
           break;
       }
       else {
           cout << "Prime" << endl;
       } break;
   }

    return 0;
}

这里循环只要执行第一次（i=2时），要么匹配到整除输出非质数退出，要么直接输出质数就break，根本不会继续遍历后面的因数。比如输入9，9%2=1，代码会直接输出Prime，但9是3*3的合数，完全不符合预期。就算你删掉else分支里的break，也会出现每遍历一个不整除的i就输出一次Prime的问题，正确的逻辑应该是等所有可能的因数都遍历完，没有找到整除的情况再输出质数。

第二版代码的核心逻辑 #

第二版用到sqrt()的写法是基于质数的数学性质优化：
如果一个数n是合数，那么它一定存在至少一个小于等于√n的正因数。
原理很简单：假设n是合数，存在两个因数a和b满足n=a*b，如果a和b都大于√n，那么a*b就会大于√n*√n =n，和n=a*b矛盾。所以我们只需要遍历从2到√n的所有整数，就能确认n有没有除了1和自身之外的因数。
这个优化把原本遍历到n-1的O(n)时间复杂度，直接降到了O(√n)，效率提升非常明显：比如判断1000003是不是质数，原来的写法要跑100万次循环，优化后的写法只需要跑1000次就能出结果。

这种优化写法有没有必要？ #

分场景看：

• 如果你只是做入门练习，只需要判断1000以内的小数字，优化前后的运行差异你几乎感知不到，但前提是你得先把基础逻辑写对，不要出现第一版里提前break的低级错误。
• 如果你要判断的数字大于1万，或者需要批量判断几十上百个数字的质数属性，这个优化就是必须的，能把原本可能要跑几秒的逻辑压缩到几毫秒就能完成。

内容的提问来源于stack exchange，提问作者Divanshu Garg