首页 > 代码库 > 【线性筛】【筛法求素数】【约数个数定理】URAL - 2070 - Interesting Numbers
【线性筛】【筛法求素数】【约数个数定理】URAL - 2070 - Interesting Numbers
素数必然符合题意。
对于合数，如若它是某个素数x的k次方（k为某个素数y减去1），一定不符合题意。只需找出这些数。
由约数个数定理，其他合数一定符合题意。
就从小到大枚举素数，然后把它的素数-1次方都排除即可。
#include<cstdio>
#include<cmath>
using namespace std;
#define MAXP 1000100
#define EPS 0.00000001
typedef long long ll;
ll L,R;
bool isNotPrime[MAXP+10];
int num_prime,prime[MAXP+10];
void shai()
{
for(long i = 2 ; i < MAXP ; i ++)
{
if(! isNotPrime[i])
prime[num_prime ++]=i;
for(long j = 0 ; j < num_prime && i * prime[j] < MAXP ; j ++)
{
isNotPrime[i * prime[j]] = 1;
if( !(i % prime[j]))
break;
}
}
}
int main()
{
scanf("%I64d%I64d",&L,&R);
shai();
int sum=0;
for(int i=0;i<num_prime;++i)
{
ll t=(ll)prime[i];
for(int j=1;;++j)
{
bool flag=1;
for(int k=prime[j-1];k<prime[j];++k)
{
if(log(t)+log(prime[i])-log(R)>EPS)
{
flag=0;
break;
}
t*=(ll)prime[i];
}
if(!flag)
break;
if(t>=L)
++sum;
}
}
printf("%I64d\n",R-L+1ll-(ll)sum);
return 0;
}
【线性筛】【筛法求素数】【约数个数定理】URAL - 2070 - Interesting Numbers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。