Timus 1086. Cryptography Solution

1086. Cryptography Solution

The main problem is...

See Original Problem

https://acm.timus.ru/problem.aspx?space=1&num=1086

Input

First line contains a positive integer k. Then k positive integers follow (one in each line). The numbers don't exceed 15000.

Output

For each number n you should output the n-th by order prime number. Each number should be in its line.

Sample

input	output
4 3 2 5 7	5 3 11 17

Notes

The prime number is a positive integer that has exactly two different positive divisors, i.e. 1 is not a prime number.

Time limit: 2.0 second
Memory limit: 64 MB

Solution: 
Solution of the problem in C++ language 

#include< bits/stdc++.h >

using namespace std;

int dp[15000];

int c=0, num=3;

int prime(int n){

    dp[0]=2;

    if(dp[n]!=-1) return dp[n];

    for(num; c<=n; num+=2){

        for(int i=0; i<=c; i++){

            if(num%dp[i]==0) break;

            if(i==c) {dp[++c]=num; break;}

        }

    }

     return dp[n];

}

int main(){

    memset(dp, -1, sizeof(dp));

    int k, n;

    scanf("%d", &k);

    for(int i=0; i<k; i++)

    {

        scanf("%d", &n);

        printf("%d\n", prime(n-1));

    }

}