admin管理员组文章数量:1594145
input | output |
---|---|
3 7 | 4 |
2 2 | 1 |
77 1010 | 924 |
/*题目收获:这道题就是反向求一个数是个合数,并且他的因子的个数是素数,那么这道题首先要解决的就是如何求一个合数的因子个数
这里我们有一个现成的简单方法可以使用:我们知道任何一个合数都可以被素数分解,也就是可以被分解成素数相乘的形式,并且这个形式
是唯一的,那么我们可以假设C=p1^a*p2^b*p3^c.....,(p1,p2,p3...都是素数),那么C的因子个数为(a+1)*(b+1)*(c+1)...,题目要求是因子
数目是素数,那么也就是(a+1)*(b+1)*(c+1)...是素数,但从这个公式我们就可以很清楚的看到,只要有两个分式相乘那么就已经不是素数
了,所以这里必须只有一个分式,也就是(a+1),(b+1),(c+1)...只能出现一个,也就是说C=p1^a*p2^b*p3^c.....只能有一个p才满足题目条件
,也就是说,C=p^n,注意这里n!=1,这个就不用解释了。这个C的范围是L-R,R的极限是10^12,因为n>=2,所以p<=10^6,所以在这里我们
只需要在2-10^6区间里素数打表即可。题目至此就可以顺利解决。*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1000010;
ll p[maxn]; //这个数组存储2-10^6的素数
ll prim[maxn]; //prim[i]==1代表i是个合数。
ll tot=1,L,R;
void prime();
ll solve(ll s)
{
ll res=s;
int i,j;
for(i=1;i<tot;i++)
{
ll t=(ll)p[i]*p[i];
ll k=2;
for(;t<=s;t*=p[i],k++)
{
if(!prim[k+1])
res--;
}
}
return res;
}
int main()
{
prime();
while(~scanf("%lld %lld",&L,&R))
{
ll ans=solve(R)-solve(L-1); L-1小技巧
printf("%lld\n",ans);
}
return 0;
}
void prime()
{
ll i,j;
tot=1;
memset(p,0,sizeof(p));
memset(prim,0,sizeof(prim));
for(i=2;i<=maxn;i++)
{
if(prim[i]==0)
{
p[tot++]=i;
for(j=i*2;j<=maxn;j+=i)
{
prim[j]=1;
}
}
}
}
版权声明:本文标题:素数筛选 素数分解 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1728179744a1148281.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论