初级守护
求思路
初级天翼
质数就是只有2个因数的数。（1不是质数）。
第一种方法：从1循环到n，如果i是n的因数，则记录因数的计数器++，如果这个计数器的值已经大于2并且i<n,则这个数不是质数，直接退出。如果计数器的值为1，则这个数为1，1不是质数，也不是质数。
其他都是质数。
时间复杂度为O(n）(线性做法）。
当然，也有更好的方法！
质数只有1和本身两个因数，所以2到n-1这些数中都不能整除n.
所以我们从2到n-1循环，如果i为n的因数，则n不是质数，退出。
如果没有退出，则判断n是否为1，为1则不是质数，不是1则是质数。
当然，第二种做法也不用从2到n-1都循环，我们来看：
n的第二大因数最大为n/2,所以在n/2+1到n-1之间一定没有n的因数。（因为(n/2+1)*2=n+2,n+2>n,n+2不是n的倍数）
我们还可以优化！
因为因数是一对一对出现的，所以循环到n/2+1是无用的，所以只要循环到sqrt(n)就可以了。
要加#include <cmath>
代码实现：
bool hs(int z)//这是一个函数。
{
for (int i=2;i<=sqrt(z);i++)//自动循环到整数，不用担心。
{
if (z%i==0)
return false;
}
return true;
}
栾峻岩在2018-08-14 23:29:04追加了内容
栾峻岩在2018-08-14 23:37:19追加了内容
判断质数的题目有:
酷町堂:
1179 素数，用函数和过程写（这道题只是套一个循环而已。）
洛谷：（全是AT题）
新手天翼
for循环套while循环
初级天翼
质数指的是只能被自己和1整除的数。
质数又称素数。
for(int i=2;i<n;i++){
if(n%i==0){
cout<<"no";
break;
}
if(n-1==i)
cout<<"yes";
}
利用以上代码可以判断一个数是否是质数。
王子健在2018-12-21 21:04:05追加了内容
这是贾老师发的讲义
王子健在2018-12-27 20:39:38追加了内容
https://jingyan.baidu.com/article/ce09321b7c871f2bfe858f60.html
https://www.sogou.com/tx?query=请问C%2B%2B中怎样求质数&hdq=sogou-site-706608cfdbcc1886&ekv=3&ie=utf8&
新手天翼
1
中级守护
函数
int zs(long long int a)
{
int l=0;
for(int i=2;i<sqrt(a);i++)
{
if(a%i==0)
l++;
}
return l;
}
核心
for(int i=0;i<n;i++)
{
cin>>a;
if(a==1)
{
cout<<"no"<<endl;
}
else if(zs(a)==0)
{
cout<<"yes"<<endl;
}
else
cout<<"no"<<endl;
}
资深守护
用if
修练者
函数代码
bool ss(int a)布尔型函数{
for (int i=2;i<=sqrt(a);i++){
if (a%i==0)
return false;}
return true;
}
新手天翼
函数
int zs(long long int a)
{
int l=0;
for(int i=2;i<sqrt(a);i++)
{
if(a%i==0)
l++;
}
return l;
}核心
for(int i=0;i<n;i++)
{
cin>>a;
if(a==1)
{
cout<<"no"<<endl;
}
else if(zs(a)==0)
{
cout<<"yes"<<endl;
}
else
cout<<"no"<<endl;
}
高级光能
函数代码
bool ss(int n)
{
for (int i=2;i<=sqrt(n);i++)
if (a%i==0)
return false;}
return true;
}
当然1和2要单独考虑
中级光能
因为我不知道题目
所以只好自己写了
自己设立一个条件
如果是质数
输出"Yes"
否则输出"No"for(int i=2;i<=n-1;i++)
{
if(n%i==0)
{
cout<<"Yes";
return 0;
}
}
cout<<"No";望采纳！！！！
~~~~~~~~~~~~~~~~~~~·
