/*
要求出[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.\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[
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\n",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\n",tt,ans);
else printf(
"Case %d: impossible\n",tt);
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10230413.html
