[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]

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

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

[D_E_N_]

Сообщение от Bargest

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

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

чтение точно с консоли. завязать рад, но сейчас эту надо 100% решить...
кстати, вот ссылка на неё: http://www.e-olimp.com.ua/problems/3608

[Bargest]

Возможно ему не нравится, что результат выводится сразу. Торт знает эти автопроверки.

[D_E_N_]

Вот собрал новую, среди 20-ти тестов стал проходить первый. По времени всё укладывается. Здесь я решил работать с файлами. Для читабельности сделал двумя функциями.

Код:

program zbs;

function IsSimple(p: cardinal): Boolean;
var
i, k : cardinal;
begin
IsSimple := True;
if (p = 0) or (p = 1) then IsSimple := False;
k := Trunc(Sqrt(p));
for i:=2 to k do
if p mod i = 0 then begin
IsSimple := False;
Break;
end;
end;

function next(num:cardinal):cardinal;
var
n:cardinal;
begin
n:=num;
if n<=2 then begin result:=2; exit; end;
inc(n);
if n or 1 <> n then inc(n);
while (n-num)<200 do
begin
if issimple(n) then break;
inc(n,2);
end;
result:=n;
end;

var
f:text;
T,i:word;
p:array[1..1049]of cardinal;
begin
assign(f,'input.txt');
reset(f);
readln(f,T);
for i:=1 to T do
readln(f,p[i]);
close(f);


for i:=1 to T do
begin
p[i]:=next(p[i]);
end;

assign(f,'output.txt');
rewrite(f);
for i:=1 to T do
writeln(f,p[i]);
close(f);
end.

[D_E_N_]

Всё, решил! Можно закрывать тему! Пришлось лишь слегка модифицировать данный пример:

Код:

program zbs;

function IsSimple(p: cardinal): Boolean;
const
base:array[1..54]of byte=(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251);
var
i, k : cardinal;  pff:boolean;
begin
IsSimple := True;
k := Trunc(Sqrt(p));
i:=1; pff:=true;
while i<55 do
begin
if p mod base[i] = 0 then begin
if p<>base[i] then
begin
IsSimple := False; pff:=false;
end;
Break;
end;
inc(i);
end;
if pff=true then
begin
i:=base[i];
while i<k do
 begin
  if p mod i = 0 then begin
   IsSimple := False;
   Break;
  end;
  inc(i,2);
 end;
end;

end;

function next(num:cardinal):cardinal;
var
n:cardinal;
begin
n:=num;
if n<2 then begin result:=2; exit; end;
inc(n);
if n or 1 <> n then inc(n);
while true do
begin
if issimple(n) then break;
inc(n,2);
end;
result:=n;
end;

var
f:text;
T,i:word;
p:array[1..1049]of cardinal;
begin
assign(f,'input.txt');
reset(f);
readln(f,T);
for i:=1 to T do
readln(f,p[i]);
close(f);


for i:=1 to T do
begin
p[i]:=next(p[i]);
end;

assign(f,'output.txt');
rewrite(f);
for i:=1 to T do
writeln(f,p[i]);
close(f);
end.

[angvelem]

Тему закрывает тот, кто её открыл.