质数、素数C++
本篇主要为个人的一些理解，若有问题欢迎提出！
什么是质数，素数：
素数值被定义为：所有大于1且不小于2的自然数值，在这些数值中不存在除了1与其自身之外的其他正整数值作为其因数值。
额小学数学。。。
质数，素数的判断：
直接根据概念进行模拟，嘿嘿嘿。
稍等一下
bool is_prime(int n){
if(n<2) return false;//小与2的数不为素数
for(int i=2;i<=sqrt(n);i++){//是到根号n原因以说明。
if(n%i==0) return false;
}
return true;
}质数，素数的筛选：
求1~n之间的素数叫素数筛选。
Eratostenes筛法：
对于任意x的倍数2x,3x,4x....都一定不是素数。这显而易见。
让我们从小数字2开始，在按顺序检查每一个数字x后（其中），找出并标记出所有这些倍数值（即2×x、3×x、4×x……直到[n/x]×x），这些数值都是合数而非素数）。这样一来就方便地执行筛选过程。
你先别急！！！
是否注意到某些合数可能会被多次标记？比如在扫描到数字2时,会将数字6标记为此类;同样地,在扫描到数字3时也会将数字6标示为此类。
因此我们可以进行优化：
对于每个扫描到的x，只需从
开始，把
，(x+1)*x,...,[n/x]*x标记为合数。于是：
void prime(int n){
memset(vis,0,sizeof(vis));//合数标记
for(int i=2;i<=n;i++){
if(vis[i]) continue;
printf("%d ",i);//是质数
for(int j=i;i*j<=n;j++) vis[i*j]=1;
}
}这个算法简单易懂且易于操作，并且其核心优势在于时间复杂度接近线性。因此，在考试环境中该算法常被采用。
线性筛法：
即使在优化成从
开始筛选仍然会有重复标记合数的情况，例如12既会被2标记也会被3标记。
具体地当扫描2时，是通过26=12来标记12的，而当扫描到3时，时通过34=12来标记12的。
so，最根本的原因是没有唯一的确定的来标记12的方式。
基于上述分析，我们采用了“从大到小逐步累加质因子”的方法来标记合数，即该数值仅限于单一的分解形式。
设数组v来维护每个数的最小质因子。具体如下：
- 依次考察从2至n的所有整数i
- 若数组元素v[i]等于其索引值i，则表明i为质数；我们可以将这些质数记录下来。
- 我们遍历所有小于等于当前值v[i]的质因数p，并更新对应位置为v[i*p] = p。这相当于在原有基础上添加一个新的质因数分解。
p不大于v[i]，所以p就是合数i*p的最小质因子。
这样每一个合数i*p只会被它的最小质因子p筛一次，时间复杂度O(n)。
void prime(int n){
memset(v,0,sizeof(v));//最小质因子
m=0;//质数数量
for(int i=2;i<=n;i++){
if(v[i]==0){
v[i]=i;
prime[++m]=i;//i是质数进行保存
}
//给当前的数i乘上一个质因子
for(int j=1;j<=m;j++){
//i有比prime[j]更小的质因子，或超出n的范围，则停止循环
if(prime[j]>v[i] || prime[j]*i>n) break;
//prime[j]是合数i*prime[j]的最小质因子
v[prime[j]*i]=prime[j];
}
}
for(int i=1;i<=m;i++) cout<<prime[j]<<" ";
}质因数分解：
对于任何一个大于1的正整数都唯一分解为有限个质数的乘积，可写为：
其中
都是正整数，
都为质数，且满足
试除法：
为了实现质因数分解的目的，我们需要遍历区间[2,√N]内的每一个整数i，并判断这些整数是否是给定数字N的一个因数。如果是，则将所有能够被i整除的因数从数字N中去除，并统计这些因数的数量d。
由于任何一个合数在其被扫描之前的所有因子均已被从集合N中删除，因此能整除N的必定是质数。从而最终我们便获得其质因数分解的结果。时间复杂度
。
void divid(int n){
m=0;
for(int i=2;i<=n;i++){
if(n%i==0){
p[++m]=i,c[m]=0;
while(i%n==0) c[m]++,n/=i;
}
}
if(n>1){//n是质数
p[++m]=n,c[m]=1;
}
cout<<n<<"=";
for(int i=1;i<m;i++) cout<<p[i]<<"^"<<c[i]<<"*";
cout<<p[m]<<"^"<<c[m];
}总结：
到此素数有关的基础讲完了，所以由此可见学c++数学基础一定要好。
别忘了相关题目一定要多做。
最后bb一句：有问题欢迎留言。