Я новичок в этом форуме и плохо знаю протоколы этого форума, так что простите меня за мое невежество. Мой вопрос связан с проблемой spoj https://www.spoj.pl/problems/KPRIMES2/. Я получаю ПРЕКРАЩЕНИЕ ВРЕМЕНИ для этой проблемы. Я думаю, что узким местом этой программы является 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
Input
Целое число, указывающее количество запросов 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<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;
}