[D_E_N_]

Вот такую задачу мне следует выполнить:

Наш юный программист Вася, прибывший на олимпиаду до её открытия, решил поучаствовать в розыгрыше олимпийской лотереи. По некоторым, только ему известным, каналам, к нему просочилась информация о том, что выигрывать будут только билеты, номера которых являются простыми числами. Подсмотрев через плечо впереди стоящего в очереди за лотерейными билетами покупателя номер купленного им билета, Васе нужно быстро посчитать, сколько человек в очереди ему нужно пропустить, чтобы ему достался билет с простым номером. Для этого ему нужно знать, какое следующее число окажется простым, и он просит в этом вашей помощи. Помогите Васе.


Технические условия
Входные данные

В первой строке находится количество тестовых случаев T (0 ≤ T ≤ 1049), а далее в T отдельных строках по одному числу – номер очередного подсмотренного билета N (0 ≤ N ≤ 4·109).

Выходные данные

Для каждого тестового случая в отдельной строке вывести номер предполагаемого счастливого лотерейного билета без ведущих нулей.


Информация о задаче
Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 4.54545
Источник: II Открытая Дистанционная Олимпиада 2012-2013 им. В.Л.Дидковского
Мои результаты: 0/2

Пример:
Пример входных данных
3
6
20
100

Пример выходных данных
7
23
101
================================================== ========

Сразу стало ясно, что о решетах Эратосфена и Аткина можно забыть.
Но как я ни бился, ничего не получается!
Первая моя реализация: olymp_lotery_v1.zip
Использовалась база простых чисел до sqrt(2*10^9)
Код оказался слишком большим, так что система отказалась принять его

Вторая реализация медленней, воркабельна, но система проверки выдала мне 80% неправильных ответов. Остальные 20% пришлись на истечение лимита времени выполнения программы.
Вот эта реализация: olymp_lotery_v2.zip


Как же быть? На С++ почти не пишу.

[M.A.D.M.A.N.]

Опять наркоманские олимпиадные задачи.

Опубликуй код, не хочется в архивах рыться.

[D_E_N_]

Опять наркоманские олимпиадные задачи.

Опубликуй код, не хочется в архивах рыться.

Первая версия уж очень велика для публикации, да и надеятся на неё без толку, размер кода не катит.

Вот, реализация второй версии:

Код:

program olymp_lotery;

function isSimple(X: cardinal): boolean;
var i: cardinal;
Begin
     result:=false;
     if x<2 then Exit;
     if not odd(x) and (x<>2)
          then exit;
     i:=3;
     while i <= sqrt(x) do
     begin
          if x mod i = 0 then Exit;
          inc(i,2);
     end;
     result:=true;
End;

var
N,i,T:cardinal;
begin
readln(T);
while t<>0 do
begin inc(n);
readln(n);
i:=N;
while (n-i)<100 do
begin
if isSimple(N) then break;
inc(N,1);
end;
writeln(N);
dec(t);
end;
end.

[Bargest]

Во-первых, для скорости sqrt(x) лучше посчитать один раз и сохранить, потом везде вызывать.
Во-вторых, в основной программе

Код:

inc(n);
readln(n);

Как-то бессмысленно.
В-третьих, если убрать вызов функции (записать ее код прямо в цикле), то несколько ускорится.

[D_E_N_]

по скорости почти всё проходит, не проходит по правильности выдачи результатов

Во-вторых, в основной программе

Код:

inc(n);
readln(n);

это я виноват: inc(n) осталось с тех пор, когда я автоматизировал ввод, чтоб по 100 раз не вводить одни и те же числа

[Bargest]

А чтение точно с консоли? Обычно автопроверялки берут из файла.

З.Ы. И в-четвертых, завязывай с олимпиадными задачками.