- jike1994's blog
质数相关讲解
- 2024-2-3 10:54:13 @
基础定义
质数:是指在大于1的自然数中,除了和它本身以外不再有其他因数的自然数。(也就是说在到中只有两个因数)
因数(约数):如果除以余数为,那么是的因数
基于理解的写法
int c=0;
for(int i=1;i<=n;i++) //枚举1到n中的所有整数
{
if(n%i==0) //说明i是n的因数
{
cnt++;//因数个数增加
}
}
if(c==2) //说明n是因数
{
}
基于定义的写法
bool st=true;//刚开始是满足的
if(n<2) //不满足定义
{
st=false;
}
for(int i=2;i<=n-1;i++) //枚举2到n-1之间的所有书
{
if(n%i==0) //说明2到n-1存在因子(n不是质数)
{
st=true;
}
}
if(st) //状态没有更新过,说明n是质数
{
}