题目描述

A positive integer is called a "prime-factor prime" when the number of its prime factors is prime. For example, 12 is a prime-factor prime because the number of prime factors of 12=2×2×3 is 3, which is prime. On the other hand, 210 is not a prime-factor prime because the number of prime factors of 210=2×3×5×7 is 4, which is a composite number.

In this problem, you are given an integer interval [l,r]. Your task is to write a program which counts the number of prime-factor prime numbers in the interval, i.e. the number of prime-factor prime numbers between l and r, inclusive.

 

输入

The input consists of a single test case formatted as follows.

l r
A line contains two integers l and r (1≤l≤r≤109), which presents an integer interval [l,r]. You can assume that 0≤r−l<1,000,000.

 

输出

Print the number of prime-factor prime numbers in [l,r].

 

样例输入

复制样例数据

1 9

样例输出

4

题目大意: 输入 l,r ,你需要输出 l-r内通过唯一分解定理得到的 因子的个数 为素数 的数 的个数 ...好绕..就那么个意思

9=3*3 (2), 8=2*2*2(3), 6 = 2*3(2),4=2*2(2)  2与3都为质数 所以 1-9  4 个 (质数排除)

题目思路:

可以想到直接唯一分解定理去拆分一个数,但是确实发现区间长度1e6,但是数的范围却到了1e9明显不合理,转换一下思维:

最大数为 1e9 那么我们只需要 打出 根号1e9≈4e4之前的的素数就完全可以,把1e9范围内的素数都筛选出来.但是区间太大了,数组根本开不到,但是a-b的区间长度却只是1e6,所以我们可以进行区间偏移,把 a - b 转移到 1-b-a+1,我们只需要用一个pair记录一下原来的数值就可以了.然后我们去用 4e4之前的素数取筛选这个区间.

那就有一个问题 如何筛选:

假设用 2去筛选 [13-20]这个区间,那 应该从14开始,每次+2,因为该区间内只要是2的倍数,都可以被2除,并且我们一次筛选完,把该数具有的2的因子,全部去除.

那么如何 确定 [13,20]区间内第一个 2的倍数是多少呢 :s=((a+prime-1)/prime)*prime  ,标红部分算出的第一个>a并且为prime倍数的数是该prime的几倍,我们来证明一下为什么:

因为 s为第一个大于等于a且是prime倍数的数是prime多少倍,我们使 prime=k 

所以 只有两种情况 边界a是k的s倍,或者边界a之上的数是k的s倍

第二种情况 a<k*s  那么 a=(s-1)*k+m   两边同时+k-1 得 a=s*k+m -1那么下取整即为s,因为m取值为 1,k 所以-1不-1无所谓

第一种情况 a=k*s  两边同时+k-1 得 a=(k+1)*s-1 a= k*s+k-1  下取整还是s,这就是为什么要+k-1否则 避免不了第二种情况

还有一种需要判断 当 2去筛 [2,10]时,第一个是2,但其是素数,所以最小是该数的2倍不能是一倍,一倍就为素数了,我们只需要筛合数.

这样就OK了,第一层遍历  前4e4个素数,第二层 去筛选[a,b]内的个数,区间转移之后 结构体或者pair维护两个值,因为只用了 sqrt(b)去筛选  还有可能 剩下一个大于sqrt()的素数,判断一下即可:

#include <bits/stdc++.h>
#define E 2.718
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
const ll INF=1e9+7;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m;
pair<ll,ll>p[maxn];
int prime[maxn];
bool vis[maxn];
bool other[maxn];
ll cnt=0;
void inint()
{
    memset(vis,true,sizeof(vis));
    vis[1]=false;
    for(int i=2;i<44000;i++)
    {
        if(vis[i])
        {
            prime[++cnt]=i;
            for(int k=2*i;k<44000;k+=i)
                vis[k]=false;
        }
    }
}
int main()
{
    memset(other,true,sizeof(other));
    inint();
    scanf("%lld%lld",&n,&m);
    vis[0]=false;
    vis[1]=false;
    for(int i=n;i<=m;i++) {p[i-n+1].first=i;p[i-n+1].second=0;}
    for(int i=1;i<=cnt;i++)
    {
        ll x=prime[i];
        for(ll k=max(2ll,(n+x-1)/x)*x;k<=m;k+=x)
        {
            while(p[k-n+1].first%x==0)
            {
                p[k-n+1].first/=x;
                p[k-n+1].second++;
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=m-n+1;i++)
    {
        if(p[i].first>1)
            p[i].second++;
        if(vis[p[i].second]) ans++;// 初始化vis把 0 和 1 至为 false,因为特殊情况只有 质数和1 质数是0,1是1
    }
    printf("%lld\n",ans);
    return 0;
}

总结:去总结一下区间筛法叭~