Bertrands Postulat
Bertrands Postulat ist ein Theorem, das besagt, dass für jede ganze Zahl
n > 1 immer mindestens eine Primzahl p existiert, die zwischen n und 2n liegt (n < p < 2n).In diesem Zusammenhang sollen Sie eine anspruchsvollere Aufgabe lösen. Gegeben ist eine Zahl
n, und Sie sollen Fragen beantworten wie beispielsweise: Wie viele Primzahlen p gibt es, für die n < p < 2n gilt?Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
t (1 ≤ t ≤ 100), die die Anzahl der Testfälle bestimmt.Die nächsten
t Zeilen enthalten jeweils eine ganze Zahl n (2 ≤ n ≤ 500 000).Ausgabe
Das Programm soll für jeden Testfall in einer eigenen Zeile ausgeben, wie viele Primzahlen sich im Bereich zwischen
n und 2n befinden.Beispiele
Eingabe | Ausgabe |
2
2
239 | 1
39 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB