SPOJ Проблема KPRIMES2

Я новичок на этом форуме и плохо знаком с протоколами этого форума, так что простите меня за мое невежество. Мой вопрос связан с проблемой spoj https://www.spoj.pl/problems/KPRIMES2/ . Я получаю TIME LIMIT EXCEED для этой проблемы. Я думаю, что узким местом этой программы является создание 10 ^ 9. Может ли кто-нибудь предложить, как улучшить это сито, более быстрый способ генерации простого числа или как решить эту проблему. Вот набросок моего алгоритма

. Эта программа генерирует все простые числа формы 2k + 1 и кодирует эти простые числа в 32-битные целые числа массива a [i], в котором неустановленный бит представляет простые числа. 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) возвращает индекс bitcnt, в котором лежит m. Наконец, в основной функции я запоминаю, сколько простых чисел находится до верхней границы m, и начал уменьшать значение, пока не получил K. Спасибо.

Редактировать: Постановка задачи из SPOJ

Входные данные

Целое число, указывающее количество запросов Q (равно 100000), и следуют Q строк, каждая из которых содержит одно целое число K от 1 до 50000000 включительно.

Выведите

Q строк с ответом на каждый запрос: K-е простое число.

Пример

Ввод: 8 1 10 100 1000 10000 100000 1000000 10000000

Выход: 2 29 541 7919 104729 1299709 15485863 179424673

#include
#include
#include
#include
#include
#include
#include
#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<>6,q_2=((j-3)>>1)&31;
                a[p_2]|=(1L<>6)-1);i++) 
     {
        //p_1=(i-3)>>6,q_1=((i-3)>>1)&31;
        cnt+=__builtin_popcount(~a[i]);
        bitcnt[bound++]=cnt;
        //cout<>1);
        if(bitcnt[mid]<=m)lo=mid+1;
        else hi=mid;

    }
    //cout<<"lo= "<0;t--) 
    {
        scanf("%d",&k);
        if(k==1) {cout<<"2"<=0;i--)
        {

            if(!(a[c] & (1L<