Contests | Virtual Contests | Problems | Submit | Runs Status | Rank List | Forum |

Time Limit: 1.0 Seconds Memory Limit: 65536K

Total Runs: 1589 Accepted Runs: 853

Given a integer p > 1, if p can be devided only by 1 and itself, we say that p is a prime number. For example, 31 can only be devided by 1 and 31, so 31 is a prime number; 12 can be devided by six numbers: 1, 2, 3, 4, 6, 12, so 12 is not a prime number. The smallest ten prime number is 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Eratosthenes was a Greek mathematician, astronomer, and geographer. He invented a method for finding prime numbers that is still used today. This method is called Eratosthenes'Sieve. A sieve has holes in it and is used to filter out the juice. Eratosthenes's sieve filters out numbers to find the prime numbers.

Eratosthenes's sieve can be used as follows to find all prime numbers smaller than or equal to a given number n:

Step1 : Put all integers between 2 and n (include 2 and n) on Eratosthenes's sieve.

Step2 : Sellect the smallest number on the sieve, suppose it is m, then m must be a prime.

Step3 : Filter out all the integers which can be devided by m from Eratosthenes's sieve.

Step4 : If m * m ≤ n, go to Step 2.

Step5 : Integers remains on the sieve are all prime numbers.

For example, if we want to find all primes between 2 and 20 using Eratosthenes's sieve,Put all integers between 2 and 20 on Eratosthenes's sieve.

Sieve : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 Prime bin : Sellect the smallest number, it's 2, so it is a prime. Then filter out all integers can be devided by 2: Sieve : 3, 5, 7, 9, 11, 13, 15, 17, 19 Prime bin : 2 Sellect the smallest number, it's 3, so it is also a prime. Then filter out all integers can be devided by 2: Sieve : 5, 7, 11, 13, 17, 19 Prime bin : 2, 3 Sellect the smallest number, it's 5, so it is also a prime. Then filter out all integers can be devided by 5: Sieve : 7, 11, 13, 17, 19 Prime bin : 2, 3, 5 Because 5 * 5 = 25 > 20, so all numbers remains on Eratosthenes's sieve are prime, put all of them into prime bin: Sieve : Prime bin : 2, 3, 5, 7, 11, 13, 17, 19Now the task is, given a number k, output the k-th smallest prime number. (You may use any way you want to solve this problem as it is correct)

The first line is an integer n, the number of test cases, n cases follows. For Each test case has an single integer k (k > 1).

A single integer per line, the k-th prime number. It is guaranted that the correct answer is smaller than 100000.

4 1 10 100 1000

2 29 541 7919

If you want to use an large arrays, Please define them as global variables. For example, if I want to use an array named arr[]:

#include ... ... ... int arr[1000000]; int main () { ...... }

Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz