判断一个数是否是素数,大概有以下3种方法:
#include<stdio.h>
int main()
{
int n,ans=0;
while(scanf("%d",&n)!=EOF)
//自己想输入多少个数就输入多少个数,直到 Ctrl+Z 时停止输入.并且 输入一个数就输出一个结果
{
if(f(n))//如果n是素数就输出Yes,,这里的f(n)是自己定义的一个函数 用来判断n是不是素数
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
1.根据素数的定义,判断能不能被除自己和1之外的数整除,从2遍历到n-1;
bool f(int n)
{
for(int i=2;i<=n-1;i++)
if(!(n%i))
return false;
return true;
}
2.由于当一个数分解成两个数的乘积是 这两个数肯定一个大于等于sqrt(n) 一个小于等于sqrt(n),所以如果我们在srqt(n)的左侧找不到n的约数,相应的在右侧也找不到,所以1方法中for循环不必循环到n-1只需要循环到sqrt(n)即可;
bool f(int n)
{
for(int i=2;i<=sqrt(n);i++)
if(!(n%i))
return false;
return true;
}
3.
首先看一个关于质数分布的规律:大于等于5的质数一定和6的倍数相邻。例如5和7,11和13,17和19等等;
证明:令x≥1,将大于等于5的自然数表示如下:
······ 6x-1,6x,6x+1,6x+2,6x+3,6x+4,6x+5,6(x+1),6(x+1)+1 ······
可以看到,不在6的倍数两侧,即6x两侧的数为6x+2,6x+3,6x+4,由于2(3x+1),3(2x+1),2(3x+2),所以它们一定不是素数,再除去6x本身,显然,素数要出现只可能出现在6x的相邻两侧。这里有个题外话,关于孪生素数,有兴趣的道友可以再另行了解一下,由于与我们主题无关,暂且跳过。这里要注意的一点是,在6的倍数相邻两侧并不是一定就是质数。
根据以上规律,判断质数可以6个为单元快进,即将方法(2)循环中i++步长加大为6,加快判断速度,代码如下:
bool f(int n)
{
if(n==2||n==3)return true;
if(n%6!=1&&n%6!=5)return false;//不在6的两侧肯定不是素数
LL tmp=sqrt(n);
for(int i=5;i<=tmp;i+=6)//在6的两侧也不一定全是素数
if(n%i==0||n%(i+2)==0)//前面为左侧,后面为右侧
return false;
return true;
}
大佬教我的方法,希望对你有点帮助吧