我找不到解决这个问题的好办法; 我需要计算范围效率中的 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
最佳答案
从 3 开始的初筛是个好主意。但是最高可能有用的素数是......? (提示:200,000,000/(? * ?))
一种可能的方法是在生成素数时向后枚举两个素数的组合,二进制搜索第二个的最高索引和第三个可能的最低索引,如果 15 * current_prime 则完全退出生成
大于 r
。
关于algorithm - 有效地计算范围内的奇数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48999401/