9度OJ 1040は前の10000個の素数を求めます

タイトルの説明:
Output the k-th prime number.
入力:
k≤10000
出力:
The k-th prime number.
サンプル入力:

3
7

サンプル出力:

5
17

この問題はk番目の素数を求めるので、kは最大10000で、ユーザーは1回入力するたびにk番目の素数を求めるので、多くの繰り返しの計算があるような気がしますが、最初は10000番目の素数を求めて、その後、ユーザーの入力に対して直接下付きで出力することができます.
ここでの鍵は,求素数という関数をどのように時間的に最適化するかである.
実は素数を求めるのは1つの比較的に古い問題で、時間の要求がない情況の下で、私達はとても簡単に2～Nの判断を行うことができて、もしその中の1つの数が与えられたNを除去することができるならば、それは素数ではないことを説明します.これは法一です.さらに最適化すると,Nの偶数が素数でない限り,Nが奇数であれば,3〜Nから判断し,いずれかの数が与えられたNを完全に除けることができれば素数ではないことを示し,ここでのステップ長は2に設定できることが分かった.さらに最適化すると,前の方法では,Nが奇数の場合,3〜ルートNから判断すればよく,同じステップ長を2に設定することが分かった.
これで、1秒以内に結果を出すことができます.実測時間は20 ms

#include 
#include 
#include 
using namespace std;

int c[10010];

bool prime(int test){
    if(test%2 == 0)
        return 0;
    for(int i=3;i<=sqrt(test);i=i+2){
        if(test%i == 0)
            return 0;
    }
    return 1;
}

int main(){
    int a;
    memset(c,0,sizeof(c));
    int k = 1;
    for(int i=2;;i++){
        if(i == 2){
            c[k] = 2;
            k++;
            continue;
        }
        if(prime(i)){
            c[k] = i;
            k++;
        }
        if(k>10000)
            break;
    }
    while(cin>>a){
        cout<