While preparing
this problem set the jury has run into the following problem: it was necessary
to send by e-mail the texts of the problems. As it is well known, e-mail is not
reliable, messages are sent not enciphered, there is a danger that someone can
intercept them. The members of the program committee wanted no participant know
the texts of the problems before the start of the contest. That‘s why they
resorted to cryptography methods in order to save the texts of the problems from
an unsanctioned reading. The jury gas worked up a new way of enciphering of a
text. It is not patented yet, so it‘s kept secret. However, we‘ll reveal you one
secret: the new algorithm is based on the work with prime numbers. In
particular, in uses a calculation of n-th by order prime
number.
Several members of
the program committee independently have worked up programs that make such
calculations, but these programs produce different answers. Each one of the
programmers is sure that his program works correctly. That‘s why the jury has
reached the deadlock and can‘t continue working. The contest is about not to
take place.
You are to help to
the jury and to save the contest. We want you to write a program that calculates
the n-th by order prime
number. The main thing is that your program should work correctly.
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 |
Hint
The prime
number is a positive
integer that has exactly two different positive divisors, i.e. 1 is not a prime
number.
Problem
Author: folklore
Problem Source: The 3rd high school children
programming contest, USU, Yekaterinburg, Russia, March 4, 2001
算法：
构建素数表，假设已经构建了素数表[p1,p2,p3……pk]，找出第k+1个素数，依次将待检测的奇数n
除以pi（1 <= i <= k），若整除，则说明n为合数，否则为素数,继续构建素数表，直至素数表中的数目达到要求
// Ural Problem 1086. Cryptography // Judgement result: Accepted // Submission Date: 10:51 16 Jan 2014 // Run Time: 0.812s // Memory used: 273KB // Language: GCC 4.7.2 C11 // // 版权所有（C）acutus (mail: acutus@126.com) // 博客地址：http://www.cnblogs.com/acutus/ // [解题方法] // 简单素数题，直接打表判断 #include<stdio.h> int a[16000]; void init() { int i, count, flag, j; flag = 1; count = 2; a[1] = 2; a[2] = 3; j = 5; while(1) { for(i = 2; i <= count; i++){ if(j % a[i] == 0) { flag = 0; break; } } if(flag){ count++; a[count] = j; } flag = 1; j += 2; if(count > 15000) break; } } void solve() { int n, N; init(); scanf("%d", &N); while(N--) { scanf("%d", &n); printf("%d\n", a[n]); } } int main() { solve(); return 0; }