有效地计算范围内的蝶形奇数

Question

对于这个问题，我找不到一个好的解决方案；我需要计算一个区间内的sphenic奇数的数量，我使用了sieve算法，但通常应该有更好的方法来做到这一点。

一个奇数是3个不同的奇素数的乘积。

我试过了，但是花了很多时间。

char t[200000001];
int dp[200000001];
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
   for(int i=3;i<200000001;i+=2)
   {
       if(t[i]==0)
        {
            for(int j=i;j<200000001;j+=i)
                t[j]++;
        }
        if(t[i]==3 && i%2)
            dp[i]=1;
   }


    for(int i=100;i<200000001;i++)
        dp[i]+=dp[i-1];

    int test=0;
    cin>>test;
    for(int tt=1;tt<=test;tt++)
    {
        int a,b;
        cin>>a>>b;
        cout<<dp[b]-dp[a-1]<<"\n";
    }

}

谢谢

编辑:我正在尝试解决这个问题：http://codeforces.com/group/HtnK54FR7R/contest/219854/problem/D

Answer 1

从3开始的质数筛子是一个很好的想法。但最高可能有用的素数是...？(提示:200000000/ (？* ?))

一种可能的方法是在生成素数时向后枚举两个素数的组合，对第二个素数的最高索引和第三个素数的最低可能索引进行二进制搜索，如果15 * current_prime大于r，则完全退出生成。