SPOJ Problem KPRIMES2

Ich bin neu in diesem Forum und nicht sehr bewusst Protokolle dieses Forums so entschuldigen Sie mich für meine Ignoranz. Meine Frage bezieht sich auf das Problem Ссылка . Ich bekomme Zeitlimit überschritten für dieses Problem.Ich denke, der Engpass dieses Programms erzeugt 10 ^ 9.Could einige vorschlagen, wie dieses Sieb zu verbessern, schneller Weg, um Prime oder wie dieses Problem zu lösen. Hier ist eine Skizze meines Algorithmus

Dieses Programm erzeugt alle Primzahlen der Form 2k + 1 und codiert diese Primzahlen in 32-Bit-Integer des Arrays a [i], in denen das nicht gesetzte Bit Primzahlen darstellt. a [0] codiert 3,5,7 ..... ..65.a [1] codiert ab 67 und so weiter. Ich habe ein Hilfsfeld bitcnt [] genommen, in dem bitcnt [i] die Summe der nicht gesetzten Bits von [0], a [1], ......... a [i] speichert. Ich benutzte Bitcnt für die binäre Suche und finde die Position der k-ten Zahl. Hier ist eine Erklärung der Funktionen. prime () - Funktion generierte Primzahlen und ich kodierte die Primzahlen auf Bits der Zahl [32 Bit unsigned integer]. Das bitcnt-Array speichert die Summe der nicht gesetzten Bits des Arrays a für die binäre Suche. bsearchupper (int m) gibt den Index von bitcnt zurück, in dem m liegt. Schließlich speichere ich in der Hauptfunktion, wie viele Primzahlen bis in den oberen Bereich von m gehen, und beginne, den Wert zu verringern, bis ich K erhalten habe. Danke.

Bearbeiten: Problemstellung von SPOJ

Eingabe

Eine Ganzzahl mit der Anzahl der Abfragen Q (entspricht 100000) und Q-Zeilen folgen, die jeweils eine Ganzzahl K zwischen 1 und einschließlich 50000000 enthalten.

Ausgabe

Q-Zeilen mit der Antwort jeder Abfrage: die K-te Primzahl.

Beispiel

Eingabe: 8 1 10 100 1000 10000 100000 1000000 10000000

Ausgabe: 2 29 541 7919 104729 1299709 15485863 179424673