C++质数的那些事（判断指数、区间筛质数、互质等等）

本文主要是介绍C++质数的那些事（判断指数、区间筛质数、互质等等），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

质数的定义：若一个正整数除了1和它自身之外不能被任何自然数整除，则该数称为质数，也叫素数。否则为合数。

质数的性质：质数的分布较为稀疏，对于一个足够大的数S，不超过S的质数大约有个，也就是说每InN个数约有一个质数，

一、判断一个整数是否是指数

代码：

#include<iostream>using namespace std;//判断传入整数是否为质数的自定义函数
bool isprime(int num)
{//特殊质数2单独判断if(num==2)return true;//偶数与特殊的数进行过滤if(num%2==0 || num<2)return false;else{for(int i=3;i*i<=num;i+=2){if(num%i==0){return false;}}return true;}
}
int main()
{int x;cin>>x;//自定义函数isprime(x)//整数x是质数返回true//整数x不是质数返回falseif(isprime(x)){cout<<"Yes";}else{cout<<"No";}return 0;
}

二、筛出给定区间的质数

代码（欧拉筛（线性筛））：

#include<iostream>
#include<cstring>const int N=1e4+10;using namespace std;bool ss[N];int main()
{//筛选出[0,n]区间的素数; int n;cin>>n;int pr[N];int cnt=0;//先初始化所有数都是素数 memset(ss,true,sizeof(ss));//排除0，1; ss[0]=ss[1]=false;for(int i=2;i<n;i++) {//选出素数if(ss[i]) pr[cnt++] = i;    for(int j=0;j<cnt&&pr[j]*i<=n;j++){//筛出非素数ss[pr[j]*i]=false;      //重复筛选,跳出循环if(i%pr[j]==0) break; }}for(int i=0;i<=n;i++) if(ss[i]) cout<<i<<" "; return 0;
} 

三、判断两个整数是否互质

代码：

#include<iostream>
#include<cstring>const int N=1e4+10;using namespace std;bool ss[N];int gcd(int a,int b)
{return b ? gcd(b, a % b) : a;
}bool coprime(int a, int b) 
{return gcd(a, b) == 1;
}int main()
{int x,y;cin>>x>>y;if(coprime(x,y))cout<<"Yes"<<endl;elsecout<<"No"<<endl;return 0;
}

代码会随个人学习进行持续更新，谢谢您的观看！

这篇关于C++质数的那些事（判断指数、区间筛质数、互质等等）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---