1、素因数分解
1、https://www.luogu.org/problemnew/show/P1075
2、https://www.luogu.org/problemnew/show/CF776B：
这道题显然可以将素数化为 1，合数变为2，然后因为长度到了100000，所以应使用埃氏筛法。但实践是一直有问题,1、要注意i等于1和2的特例；2、
3、整数惟一分解定理：任意一个大于0的正整数都能被表示成若干个素数的乘积且表示方法是唯一的；整理可以将相同素数的合并；可以得到公式————n = P1^a1 * P2^a2 * …………*Pn^an (P1 < P2 < ……Pn);有一些小细节要注意
#include<iostream> #include<cstdio> #include<cstdlib> using namespace std; int n; int a[10000]; int p[10000]; int main(){ scanf("%d",&n); int m=n;//注意应用m代替n，不用中途会变小 int count=0; for(int i=2;i*i<=n;i++){ while(m%i==0){//因为一定会把带有这个素数的除完，所以肯定不会被合数除 p[i]++; //这样写好写方便 m/=i; } } if(m>1)p[m]++;//重点！！最后可能会多一个出来，要把本身也算 for(int i=2;i<=n;i++) if(p[i]) printf("%d^%d ",i,p[i]); }
2、素数筛法
1、埃氏筛法：
埃氏筛法的中心还是很好理解，只是要注意从j=i*i开始，降低时间消耗
#include<iostream> #include<cstdio> #include<cstdlib> using namespace std; int n,a[1001001]; int main(){ scanf("%d",&n); a[0]=a[1]=1;//将0和1特判，素数 为0 for(int i=2;i*i<=n;i++){ if(!a[i]){ for(int j=i*i;j<=n;j+=i) a[i]=1; } } for(int i=2;i<=n;i++){ printf("%d ",a[i]); } return 0; }
2、Prime Distance：https://www.luogu.org/problemnew/show/UVA10140 这道题还是应用埃氏筛法，但是这道题显然数据太大，不能筛完全部素数，所以我们可以考虑先筛出2到根号r的所有素数（为了节省时间，要先做，直接到100000>根号的2^31-1）,然后注意到l和r间的的范围是有限的，只有1000000,所以就用已算出的素数将其筛掉，即标记i*p-l 为合数（减去l是精华！）
，然后再用prime2将l到r的素数记录下来即可。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; int prime1[100100]; long long prime2[100100];//注意大小，要用ll bool check[1000100];//用bool占用的空间较小 int count1=1,count2; int main(){//往往错在最没想到会错的地方 for(int i=2;i*i<=100100;i++) if(!check[i]){//写错 prime1[count1++]=i; for(long long j=i*i;j<=100100;j+=i)//j应+=i check[j]=1;//写错 } /* for(int i=1;i<=10;i++) cout<<prime1[i]<<" ";*/ long long L,R; long long mina,maxa,x1,x2,y1,y2; while(scanf("%lld%lld",&L,&R)!=EOF){ mina=131313133,maxa=-1; x1=x2=y1=y2=0; memset(check,0,sizeof(check)); count2=0; L=max(L,(long long)2);//要注意1是特例 for(long long i=1;prime1[i]*prime1[i]<=R&&i<count1;i++){//注意在prime1中素数只有count1个 long long s=L/prime1[i]+(L%prime1[i]>0);//括号位置！因为范围在L，R间l/prime向下取整，除非正好相等否则要加1 if(s==1)s=2;//因为prime本身是素数，如果*1也还是素数，如果从1开始就会把素数判成合数 for(long long j=s;j*prime1[i]<=R;j++)//j*prime[i]只有小于r才有意义 check[j*prime1[i]-L]=1; } /* for(int i=0;i<335;i++) printf("%d ",check[i]);*/ for(long long i=0;i<=R-L;i++)//重点，i的取值范围，l可能正好是素数，最多到R-l if(!check[i])prime2[count2++]=i+L;//count2记区间有几个素数 /* for(int i=0;i<count2;i++) printf("%d ",prime2[i]);*/ for(int i=1;i<count2;i++){ if(prime2[i]-prime2[i-1]<mina){ mina=prime2[i]-prime2[i-1]; x1=prime2[i-1],y1=prime2[i]; } if(prime2[i]-prime2[i-1]>maxa){ maxa=prime2[i]-prime2[i-1]; x2=prime2[i-1],y2=prime2[i]; } } if(count2<2) printf("There are no adjacent primes. "); else{ printf("%lld,%lld are closest, %lld,%lld are most distant. ",x1,y1,x2,y2); } } return 0; }
3.利用埃氏筛法优化质因数分解，只要找到在判素数时同时找到最小素因数即可
#include<iostream> #include<cstdio> #include<cstdlib> #include<vector> using namespace std; int prime[1001000],minf[1001000];//确定最小质因数 vector<int > ret; //做确定素数时要考虑取值范围，是否要用long long来定义 void erato(int n){ prime[0]=prime[1]=0; minf[0]=0;minf[1]=1;//特例 for(int i=2;i<=n;i++) prime[i]=1,minf[i]=i;//当他本身是最小的要么是素数，要么还没找到 for(int i=2;i*i<=n;i++) if(prime[i]){ for(int j=i*i;j<=n;j+=i){ prime[j]=0; if(minf[j]=j) minf[j]=i; } } } int found(int x){ while(x>1){ ret.push_back(minf[x]); x/=minf[x]; } } int main(){ int n; scanf("%d",&n); erato(n); found(n); return 0; }
4.阶乘分解：将阶乘n!（1<=n<=10^6）分解素因数，以唯一分解形式给出pi和ri 朴素想法将1~n质因数分解，再将相同的pi累加,但是这样显然过不了
然后我们考虑，其实在1~n中，素数也就那几个，所以先找出全部的素数，然后对于每个素数，
，N/p^k向下取整就是p出现的个数（通过举例可验证或，因为在n内，对于p的倍数有n/p个，如果有的是p^2的倍数，那么也出现n/p^2个，同理可证）
#include<iostream> #include<cstdio> #include<cstdlib> using namespace std; int n,prime[10010],cs[10010],f[1010010]; int cnt=1; void foun(){ for(int i=2;i<=n;i++){ if(!f[i]){ prime[cnt]=i;cnt++; for(int j=i*i;j<=n;j+=i) f[j]=1; } } cnt--; } void jl(){ for(int i=1;i<=cnt;i++){ for(int j=prime[i];j<=n;j*=prime[i]) cs[i]+=n/j; } } int main(){ scanf("%d",&n); foun();//先找出一到n中所有存在的质数 jl();//找每个素数被用的次数 for(int i=1;i<cnt;i++) printf("%d^%d+",prime[i],cs[i]); printf("%d^%d",prime[cnt],cs[cnt]); }
5.欧拉筛法（线性筛）：利用 i 和素数表中的素数 prime[j] 去筛除 i*prime[j] ，为了确保i*prime[j] 只被素数 prime[j] 筛除过这一次，要确保 prime[j] 是i*prime[j] 中最小的素因子，即 i 中不能有比 prime[j] 还要小的素因子
//线性筛法 void Euler(){ for(int i=2;i<=n;i++){ if(!isprime[i])prime[++prime[0]]=i; else{ for(int j=1;j<=prime[0]&&prime[j]*i<=n;j++){//每次用已确定的素数来筛 isprime[prime[j]*i]=1; if(i%prime[j]==0)break;//这句话是线性筛精华所在，保证每个数只被 //它最小的素因子筛去； } } } }