--- title: "判断质数-素数" created: 2025-11-28 tags: - 算法 --- # 判断质数/素数 ## 题目 [试除法判定质数](https://www.acwing.com/problem/content/description/868/) ![[image-4cec9db0.png]] ## 思路分析 首先 什么是质（素）数 只有1和它本身两个约数的数叫做素数 那么暴力其实就很好写了 从2枚举到n-1 只要有一个数可以被n整除 就说明n不是素数 ```cpp bool is_prime(int n){ if(n < 2) return false; //2是最小的质数，如果n小于2，那n肯定就不是质数 for(int i = 2;i < n;i ++){ if(n % i == 0){ return false; } } return true; } ``` 填空题这样写无所谓 方便 又不要求时间 如果出现在编程题里面 这种O(n)的方法显然是不行的 考虑一下优化 我们是在2到n-1里找一个能被n整除的数 如果找到了就说明不是素数 但其实可以发现 这些数都是成对出现的 比如12的约数有2 6 ，3 4 也就是说我找到了2就没必要再去找个6了 找到了3也没必要再去找后面的4了 所以可以把枚举范围缩小到sqrt(n) ![[image-0873c35b.png]] ```cpp //直观来写 bool is_prime(int n){ if(n < 2) return false; for(int i = 2;i <= sqrt(n);i ++){ if(n % i == 0){ return false; } } return true; } //不推荐sqrt的写法 调用该函数运行很慢，每次执行时都要运算一遍 //考虑到每次调用的优化 其实可以用变量存好sqrt的值 bool is_prime(int n){ if(n < 2) return false; int x = sqrt(n); for(int i = 2;i <= x;i ++){ if(n % i == 0){ return false; } } return true; } //还有一种常见的写法 bool is_prime(int n){ if(n < 2) return false; for(int i = 2;i * i <= n;i ++){ if(n % i == 0){ return false; } } return true; } //也不推荐 若i值比较大的话 会存在爆int的风险 ``` **正解：** ```cpp bool is_prime(int n){ if(n < 2) return false; for(int i = 2;i <= n / i;i ++){ if(n % i == 0){ return false; } } return true; } ``` **总结：** 质数定义：一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数，这个数就是质数。 给定一个数 x,判断 x 是否为质数： 用 x 除以 2 ~ x - 1 中的每个数，如果出现了余数为 0,则这个数不是质数，如果没有出现余数为 0,则这个数是质数。 **优化：** 一个数 x 分解成两个数的乘积，则这两个数中，一定有一个数大于根号 x，一个数小于根号x。 所以，可以用 x 除以 2 ~ 根号x 中的每个数，如果出现了余数为 0,则这个数不是质数，如果没有出现余数为 0,则这个数是质数。 ## 代码实现 ```cpp #include using namespace std; int n; bool is_prime(int x){ if(x<2) return false; for(int i=2;i<=x/i;i++) if(x%i==0) return false; return true; } int main() { cin>>n; while(n--){ int x; cin>>x; if(is_prime(x)) cout<<"Yes"<