SPOJ 问题 KPRIMES2

Question

我是这个论坛的新手，不太了解这个论坛的协议，所以请原谅我的无知。我的问题与 spoj 问题有关 https://www.spoj.pl/problems/KPRIMES2/。我遇到这个问题的时间限制超出。我认为这个程序的瓶颈是生成 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() 函数生成素数，并将素数编码到 number[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; 
}

Answer 1

考虑进一步压缩您的主要存储。例如，在 2*3*5*7*11=2310 的每个块中，正好有 1*2*4*6*10=480 个数字不具有 11 或更少的质因数，您可以将其打包为 15数组条目而不是（大约）36 个。这将消除筛选出这些小因素的几亿位操作。您必须更改位数组的索引；几个长度为 2310 的常量数组给出位索引（如果存在）和数组元素偏移量在这里会有所帮助，并且一个类似的数组（长度为 480）将位位置转换回模 2310 的值。