判断质数/素数
题目 试除法判定质数
思路分析
首先 什么是质（素）数 只有1和它本身两个约数的数叫做素数
那么暴力其实就很好写了 从2枚举到n-1 只要有一个数可以被n整除 就说明n不是素数
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)
//直观来写
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的风险
正解：
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,则这个数是质数。
代码实现
#include<bits/stdc++.h>
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"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
💬 评论