我是这个论坛的新手，不太了解这个论坛的协议，所以请原谅我的无知。我的问题与 spoj 问题https://www.spoj.pl/problems/KPRIMES2/有关。我正在为这个问题获得 TIME LIMIT EXCEED。我认为这个程序的瓶颈是生成 10^9。有人可以建议如何改进这个筛子，更快地生成素数或如何解决这个问题。这是我的算法的草图
该程序生成所有形式为 2k+1 的素数，并将这些素数编码为数组 a[i] 的 32 位整数，其中未设置的位表示素数。a[0] 编码 3,5,7.......65 .a[1] 从 67 开始编码，依此类推。我采用了一个辅助数组 bitcnt[]，其中 bitcnt[i] 存储了 a[0]、a[1]、.........a[i] 的未设置位的总和。我使用bitcnt进行二进制搜索并找到第k个数字的位置。这里是函数的位解释。prime() 函数生成素数，我将素数编码为数字 [32 位无符号整数] 的位。bitcnt 数组存储数组 a 的未设置位的总和，用于二进制搜索。bsearchupper(int m) 返回 m 所在的 bitcnt 的索引。最后在主函数中，我存储了多少素数达到 m 的上限并开始减小值直到我得到 K。谢谢。
编辑：来自 SPOJ 的问题陈述
输入
一个整数，表示查询的数量 Q（等于 100000），接下来是 Q 行，每行包含一个介于 1 和 50000000 之间的整数 K。
输出
Q 行与每个查询的答案：第 K 个素数。
例子
输入：8 1 10 100 1000 10000 100000 1000000 10000000
输出：2 29 541 7919 104729 1299709 15485863 179424673
#include<cstdio>
#include<vector>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#define Lim 1000000000
using namespace std;
unsigned int a[(Lim>>6)+10],bitcnt[(Lim>>6)+10];
int bound;
void prime()
{
int p_1,q_1,p_2,q_2,Ub=sqrt(Lim*1.0);
for(int i=3;i<=Ub;i+=2)
{
p_1=(i-3)>>6,q_1=((i-3)>>1)&31;
if(!(a[p_1] & (1L<<q_1)))
for(int j=i*i;j<Lim;j+=i)
if(j&1)
{
p_2=(j-3)>>6,q_2=((j-3)>>1)&31;
a[p_2]|=(1L<<q_2);
}
}
int cnt=0;bound=0;
for(int i=0; i<=((Lim>>6)-1);i++)
{
//p_1=(i-3)>>6,q_1=((i-3)>>1)&31;
cnt+=__builtin_popcount(~a[i]);
bitcnt[bound++]=cnt;
//cout<<bound-1<<"---"<<bitcnt[bound-1]<<endl;
}
//cout<<cnt<<endl;
}
int bsearchupper(int m)
{
int lo=0,hi=bound,mid;
while(lo<hi)
{
mid=lo+((hi-lo)>>1);
if(bitcnt[mid]<=m)lo=mid+1;
else hi=mid;
}
//cout<<"lo= "<<lo<<" mid= "<<mid<<" hi= "<<hi<<endl;
return lo;
}
int main()
{
//clock_t start,end;
//start=clock();
prime();
int t,k,c,ret,w;
for(scanf("%d",&t);t>0;t--)
{
scanf("%d",&k);
if(k==1) {cout<<"2"<<endl;continue;}
k=k-2;
c=bsearchupper(k);
ret=bitcnt[c],w=32*(c+1);
for(int i=31;i>=0;i--)
{
if(!(a[c] & (1L<<i)))
{
ret--;
if(ret==k) printf("%d\n",3+(w-1)*2);
}
w--;
}
}
//end=clock();
//cout<<((end-start)/(double)CLOCKS_PER_SEC)<<endl;
}