№1086
http://acm.timus.ru/problem.aspx?space=1&num=1086
ЖМИ ДАЛЕЕ>>>
РЕШЕНИЕ:
PASCAL
Var
A:Array[1..15000] of Longint;
P,I,J,N,T: LongInt;
F: Boolean;
Begin
Readln(N);
P:=0;
For I:=2 to MaxLongInt do begin
F:=True;
For J:=1 to P do begin
If (I mod A[J] = 0) then begin
F:=False;
Break;
End;
If A[J]>=Sqrt(I) then Break;
End;
If F then begin
Inc(P);
A[P]:=I;
End;
If P=15000 then break;
End;
For I:=1 to N do begin
Readln(T);
Writeln(A[T]);
End;
End.
1086. Криптография
Ограничение времени: 2.0 секунды
Ограничение памяти: 16 МБ
Ограничение памяти: 16 МБ
При подготовке данного комплекта задач жюри столкнулось со следующей проблемой: нужно было передавать по электронной почте тексты задач. Как известно, электронная почта ненадёжна, сообщения передаются открытым текстом, и существует опасность, что кто-нибудь их перехватит. Членам программного комитета вовсе не хотелось, чтобы задачи стали известны участникам раньше начала соревнования, поэтому они прибегли к методам криптографии. Жюри разработало совершенно новый способ шифрования текста, но он пока не запатентован и поэтому держится в секрете. Впрочем, одну тайну мы вам всё же откроем, новый алгоритм основан на работе с простыми числами и, в частности, использует вычисление n-го по счёту простого числа.
Несколько членов программного комитета, независимо друг от друга, разработали программы, производящие такие вычисления, но эти программы выдают разные ответы. Каждый уверен, что он написал свою программу правильно, поэтому жюри встало в тупик и не может продолжать свою работу.
Вы должны помочь жюри и спасти соревнования. Напишите программу, вычисляющую n-е по счёту простое число, и, самое главное, она должна работать правильно!
Исходные данные
В первой строке находится ровно одно целое число k, задающее количество чисел в списке. За ним следуют k целых чисел, по одному в строке. Все числа положительные и не превосходят 15000.
Результат
Для каждого числа n из списка вы должны вывести n-е по счёту простое число. Ответ для каждого числа должен находиться в отдельной строке.
Пример
| исходные данные | результат |
|---|---|
4 3 2 5 7 | 5 3 11 17 |
Подсказка
Простое число — это целое положительное число, которое имеет ровно два различных положительных делителя, т.е. 1 не является простым числом.
Автор задачи: фольклор
Источник задачи: Третье командное соревнование школьников Свердловское области по программированию, 4 марта 2001
Источник задачи: Третье командное соревнование школьников Свердловское области по программированию, 4 марта 2001