/* 要求出[1,R]之间的质数会超时，但是要判断[L,R]之间的数是否是素数却不用筛到R 因为要一个合数n的最大质因子不会超过sqrt(n) 所以只要将[2,sqrt(R)]之间的素数筛出来，再用这些素数去筛[L,R]之间的合数即可 */ #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define ll long long ll L,R,ans[1000005]; int v[10000007],prime[1000000],m,isprime[1000005]; void init(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; } for(int j=1;j<=m;j++){ if(prime[j]>v[i] || prime[j]>n/i) break; v[i*prime[j]]=prime[j]; } } } int main(){ init(10000000);//打表求出[2,10^7]之内的质数 while(scanf("%lld%lld",&L,&R)==2){ if(L==1) L=2; memset(isprime,0,sizeof isprime); for(ll i=1;i<=m;i++){ if(prime[i]>sqrt(R)+1)break;//超过sqrt(R)的质数就不用筛了 for(ll j=(L-1)/prime[i]+1;prime[i]*j<=R;j++) if(j>1)isprime[prime[i]*j-L]=1; } ll L1,R1,L2,R2,Max=-1,Min=99999999,tot=0; for(ll i=0;i<=R-L;i++) if(!isprime[i]) ans[tot++]=i+L; if(tot<=1) { puts("There are no adjacent primes."); continue; } for(int i=1;i<tot;i++){ if(Max<ans[i]-ans[i-1]){ Max=ans[i]-ans[i-1]; L1=ans[i-1],R1=ans[i]; } if(Min>ans[i]-ans[i-1]){ Min=ans[i]-ans[i-1]; L2=ans[i-1],R2=ans[i]; } } printf("%lld,%lld are closest, %lld,%lld are most distant. ",L2,R2,L1,R1); } }
/*阶乘分解：给定一个n，求分解n！的质因数，输出总共有多少质因数
思路：筛出1-N所有的质因数，质因数p在n!中出现的次数即p在1-n所有数中出现的次数之和，那么p出现了n/p次，p*p出现了n/p*p次，。。累加即可
*/
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; #define ll long long int n,m,prime[1000005],v[1000005]; void init(int n){ memset(prime,0,sizeof prime); memset(v,0,sizeof v); m=0; for(int i=2;i<=n;i++){ if(v[i]==0){ v[i]=i; prime[++m]=i; } for(int j=1;j<=m;j++){ if(prime[j]>v[i] || prime[j]*i>n) break; v[i*prime[j]]=prime[j]; } } } int main(){ init(1000005); while(scanf("%d",&n)==1){ ll ans=0; for(int i=1;i<=m;i++){ if(prime[i]>n) break; int j=prime[i]; while(j<=n){ ans+=n/j; j*=prime[i]; } } printf("%d ",ans); } }
//质数筛法 /*Era筛： 复杂度：O(nloglogn)非常接近线性 原理：任何质数x的倍数：2x,3x,...都是合数，优化后只要筛 >=x*x的数即可 */ void primes(int n){ memset(v,0,sizeof v);//合数标记 for(int i=2;i<=n;i++){ if(v[i]) continue; for(int j=i;i*j<=n;j++) v[i*j]=1; } } /* 线性筛 复杂度：O(n) 原理：每个数只被它最小的数筛一次 */ void primes(int n){ memset(v,0,sizeof v);//每个数的最小质因子 memset(prime,0,sizeof prime);//质数集合 m=0;//质数数量 for(int i=2;i<=n;i++){ if(v[i]==0){//i是质数 v[i]=i; prime[++m]=i; } for(int j=1;j<=m;j++){ if(prime[j]>v[i] || prime[j]*i>n) break;//如果i有比prime[j]小的质因子，或者超出n范围 v[i*prime[j]]=prime[j];//prime[j]是i*prime[j]的最小质因子 } } } //质因数分解 /* 试除法 复杂度：O(sqrt(N)) 原理：对于给定的n，枚举[2,sqrt(n)]中的每个数d，若n能整除d，则把n中所有的d除去 */ void divide(int n){ memset(p,0,sizeof p);//n的质因子 memset(c,0,sizeof c);//个质因子的幂 m=0; for(int i=2;i<=sqrt(n);i++){ if(n%i==0){//i必定是质数 p[++m]=i,c[m]=0; while(n%i==0)n/=i,c[m]++; } } if(n>1) p[++m]=n,c[m]=1;//n是质数 }
hdu1124求阶乘的尾零
/* 阶乘求尾零 那就只要求出n!阶乘质因数分解后有多少2和5即可 */ #include<bits/stdc++.h> using namespace std; #define ll long long ll ans,n,ans1,ans2; int main(){ int T; cin>>T; for(int tt=1;tt<=T;tt++){ cin>>n; ans1=ans2=0; ll tmp=n; while(n>=2) ans1+=n/2,n/=2; while(tmp>=5) ans2+=tmp/5,tmp/=5; ans=min(ans1,ans2); cout<<ans<<endl; } }
light1138 二分答案，最后不要忘记验证答案，
#include<bits/stdc++.h> using namespace std; #define maxn 100005 #define ll long long ll n; int judge(ll mid){ ll res=0; while(mid>=5) res+=mid/5,mid/=5; if(res>=n)return 1; return 0; } int main(){ int T; cin>>T; for(int tt=1;tt<=T;tt++){ cin>>n;//要有n个5因子 ll mid,l=5,r=1000000000,ans=-1; while(l<=r){ mid=l+r>>1; if(judge(mid)) ans=mid,r=mid-1; else l=mid+1; } if(ans!=-1){ ll tmp=ans,cnt=0; while(tmp>=5) cnt+=tmp/5,tmp/=5; if(cnt!=n)ans=-1; } if(ans!=-1) printf("Case %d: %lld ",tt,ans); else printf("Case %d: impossible ",tt); } }