/*
要求出[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[];
int v[],prime[],m,isprime[];
void init(int n){
memset(v,,sizeof v);
m=;
for(int i=;i<=n;i++){
if(v[i]==){
v[i]=i;
prime[++m]=i;
}
for(int j=;j<=m;j++){
if(prime[j]>v[i] || prime[j]>n/i) break;
v[i*prime[j]]=prime[j];
}
}
} int main(){
init();//打表求出[2,10^7]之内的质数
while(scanf("%lld%lld",&L,&R)==){
if(L==) L=;
memset(isprime,,sizeof isprime);
for(ll i=;i<=m;i++){
if(prime[i]>sqrt(R)+)break;//超过sqrt(R)的质数就不用筛了
for(ll j=(L-)/prime[i]+;prime[i]*j<=R;j++)
if(j>)isprime[prime[i]*j-L]=;
} ll L1,R1,L2,R2,Max=-,Min=,tot=;
for(ll i=;i<=R-L;i++)
if(!isprime[i]) ans[tot++]=i+L; if(tot<=) {
puts("There are no adjacent primes.");
continue;
}
for(int i=;i<tot;i++){
if(Max<ans[i]-ans[i-]){
Max=ans[i]-ans[i-];
L1=ans[i-],R1=ans[i];
}
if(Min>ans[i]-ans[i-]){
Min=ans[i]-ans[i-];
L2=ans[i-],R2=ans[i];
}
}
printf("%lld,%lld are closest, %lld,%lld are most distant.\n",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[],v[];
void init(int n){
memset(prime,,sizeof prime);
memset(v,,sizeof v);
m=;
for(int i=;i<=n;i++){
if(v[i]==){
v[i]=i;
prime[++m]=i;
}
for(int j=;j<=m;j++){
if(prime[j]>v[i] || prime[j]*i>n) break;
v[i*prime[j]]=prime[j];
}
}
} int main(){
init();
while(scanf("%d",&n)==){
ll ans=;
for(int i=;i<=m;i++){
if(prime[i]>n) break;
int j=prime[i];
while(j<=n){
ans+=n/j;
j*=prime[i];
}
}
printf("%d\n",ans);
}
}
//质数筛法
/*Era筛：
复杂度：O(nloglogn)非常接近线性
原理：任何质数x的倍数：2x,3x,...都是合数，优化后只要筛 >=x*x的数即可
*/
void primes(int n){
memset(v,,sizeof v);//合数标记
for(int i=;i<=n;i++){
if(v[i]) continue;
for(int j=i;i*j<=n;j++) v[i*j]=;
}
} /*
线性筛
复杂度：O(n)
原理：每个数只被它最小的数筛一次
*/
void primes(int n){
memset(v,,sizeof v);//每个数的最小质因子
memset(prime,,sizeof prime);//质数集合
m=;//质数数量
for(int i=;i<=n;i++){
if(v[i]==){//i是质数
v[i]=i;
prime[++m]=i;
}
for(int j=;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,,sizeof p);//n的质因子
memset(c,,sizeof c);//个质因子的幂
m=;
for(int i=;i<=sqrt(n);i++){
if(n%i==){//i必定是质数
p[++m]=i,c[m]=;
while(n%i==)n/=i,c[m]++;
}
}
if(n>) p[++m]=n,c[m]=;//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=;tt<=T;tt++){
cin>>n;
ans1=ans2=;
ll tmp=n;
while(n>=)
ans1+=n/,n/=;
while(tmp>=)
ans2+=tmp/,tmp/=;
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=;
while(mid>=)
res+=mid/,mid/=;
if(res>=n)return ;
return ;
}
int main(){
int T;
cin>>T;
for(int tt=;tt<=T;tt++){
cin>>n;//要有n个5因子
ll mid,l=,r=,ans=-;
while(l<=r){
mid=l+r>>;
if(judge(mid))
ans=mid,r=mid-;
else l=mid+;
} if(ans!=-){
ll tmp=ans,cnt=;
while(tmp>=)
cnt+=tmp/,tmp/=;
if(cnt!=n)ans=-;
} if(ans!=-)
printf("Case %d: %lld\n",tt,ans);
else printf("Case %d: impossible\n",tt);
}
}