algorithm - 有效地计算范围内的奇数

Question

我找不到解决这个问题的好办法；我需要计算范围效率中的 sphenic 奇数的数量我使用过筛算法，但通常应该有更好的方法来做到这一点。

奇数是 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 开始的初筛是个好主意。但是最高可能有用的素数是......？ (提示:200,000,000/(? * ?))

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