Pascal: duże sito Eratostenesa

Chodzi mi o zadanie piąte z tegorocznej matury. Chodzi w nim m.in. o sprawdzanie czy liczby są pierwsze. Podobno najlepsze do tego jest sito Eratostenesa. Problem stanowi duży zakres, liczby mają być szukane do 100000. Wprowadzam tablicę 100000-elementowej, za pomocą wyrażenia
var t:array[1..100000] of boolean, ale wyrzuca błąd 'ordinal type expected', maksymalną liczbą jest chyba 65535. Co z tym zrobić?

Właściwie, to o co chodziło w tym zadaniu? Aby wypisywał wszystkie liczby pierwsze do 1000000?

Nalezalo znaleŹĆ wszystkie liczby pierwsze od 100 do 100000, potem z nich znaleŹĆ te, ktorych suma cyfr jest liczba pierwsza. Potem nalezalo znaleŹĆ z tych co zostaly takie, ze ich suma cyfr w systemie binarnym tez jest liczba pierwsza. Ja nie bawilem sie w sito, tylko zrobilem zwykle sprawdzanie reszty z dzielenia dla wszystkich tych liczb. Troche to trwalo (jakies 15s), ale najwazniejsze, ze dziala.

U mnie to trwało prawię minutę, więc zastanawiam się nad łatwiejszą metodą :)

Stwórz sito zawierające tylko liczby nieparzyste począwszy od 3 czyli liczba o indeksie I to 2I+1. W ten sposób zmieścisz się w zakresie a program będzie działał szybciej.

ps. 2i + 1 = i shl 1 or 1

znaleŹĆ wszystkie liczby pierwsze od 100 do 100000,

wrzucać robić 100 kb na stos albo do sekcji danych programu to trochę głupio. dynamicznie to lepiej by było utworzyć, jakieś new (albo co tam w Delphi jest) raczej już ograniczenia nie ma. albo zastosować algorytm, który przechowuje w tablicy tylko znalezione liczby.

w pseudokodzie pascalo-cpplusowym:

tablica = {2}
pierwsze = 1
for n=3 to 100 000 {
   zlozona = false
   for i=1 to pierwsze
      if(n mod tablica[i] == 0) zlozona=true
   if(zlozona==false) {
      zwieksz [pierwsze]
      dodaj [n] do [tablica]
   }
}
wypisz [tablica]

we free pascalu nie było problemów. W Turbo mogłeś utworzyć dwie tablice, działało by to tylko odrobinę wolniej.

Ale i tak dużo na tym zadaniu mi chyba utną, bo uznałem, że 1 jest liczbą pierwszą ;(. A takie miałem eleganckie rozwiązanie :(. Sorry za wyrażenie, ale jakieś 3-5 pkt psu w dupe (1-2 za wyniki w tabelki i pewnie 1-2 za algorytm)

edit: nie zauważyłem wypowiedzi hes - rzeczywiście ganckie rozwiązanie

Rani napisał, że 100 KB na stosie czy w segmencie danych wygląda głupio, czemu?
Albo się da, albo nie, a wtedy sterta też nie pomoże. Jeżeli 100'000 nie jest ORDINAL'ne, znaczy, że mamy do czynienia z 16 bitnym kompilatorem, dla którego maksymalnym rozmiarem dla dowolnej struktury jest 64 kilo.

Ciekawym czy wszędzie gdzie pojawiło się takie zadanie, egzaminowani korzystali z 16 bitowego staruszka, czy też szkoła miała dowolność, a wtedy wyniki stają się nieporównywalne.
Nie jest to może zasługa mojego ulubionego ministra, ale z pewnością jeszcze jeden powód, dla którego go tak ku.... lubię :D

Tu optimum to rzeczywiście sito (jak często zresztą).
Przesiewać można tylko liczby nieparzyste jak zaproponował Hes, skoro szukamy liczb >100 to odpada specjalne traktowanie dwójki (jedynej parzystej liczby pierwszej).

Sposób zaproponowany przez Ranidesa ma wadę (poza większą złożonością), będziemy jeszcze testować "pierwszość" kilku liczb (sumy cyfr). Łatwiej zrobić to dysponując tablicą mówiącą o tym czy liczba jest pierwsza, niż dysponując listą pierwszych (wtedy na podwyższenie oceny wpłynęłoby skorzystanie np. z bisekcji).

WiktorDelphi zrobił sobie funkcję testującą pierwszość przez badanie reszt z dzielenia. I takie rozwiązanie jest dobre, gdy mamy ograniczony czas (można zrobić to lepiej lub gorzej). I sam pewnie tak bym zrobił, a poprawiał gdyby starczyło czasu.

Jak oceniać rozwiązanie takiego zadania? Sprawdzić wynik, działa albo nie.
Dodać jakiś plus za dowcip (nie szukanie dzielników większych od pierwiastka, bisekcja, kwadrat w sicie), albo minus (za nieczytelność, brak powyższych zalet).

Może odwiedza nas (tu na 4p) jakiś nauczyciel, który egzaminował w tym roku i powie czy zadanie brzmiało tak jak podał WiktorD, jakimi narzędziami dysponowali abiturienci, jak należało oceniać rozwiązania?

ciekawym, jakby oceniono moje rozwiązanieconst
n2=50000; { 100'000 / 2 }
var
t:array[1..n2] of boolean;
i,j,s,l:word;
k,i21:longint;
begin
for i:=1 to N2 do
t[i]:=true;
for i:=1 to trunc(sqrt(2.0N2)) div 2 do begin
if t[i] then begin
j:=(ii+i)2;
while j<=N2 do begin
t[j]:=false;
j:=j + 2i + 1
end
end
end;
{t[i] mówi o pierwszości liczby 2i+1}
l:=0;
for i:=1 to n2 do
if t[i] then begin {2i+1 jest pierwsze }
i21:= longint(i)*2 + 1;
k:= i21;
s:= 0; {s - suma cyfr }
while k>0 do begin
s:= s + k mod 10;
k:= k div 10;
end;
if odd(s) and t[(s-1) div 2] then begin
s:=0;
k:=i21;
while k>0 do begin
s:= s + k mod 2;
k:= k div 2;
end;
if odd(s) and t[(s-1) div 2] then begin
l:=l+1;
write(i21:8);
end
end
end;
writeln;
writeln(l, ' takich liczb');
end.

mgr.Dobrowolski napisał(a)

skoro szukamy liczb >100 to odpada specjalne traktowanie dwójki

i tu byś niestety wpadł, tak jak ja zresztą :/. Co z tego, że liczby są > 100, jak ich suma binarna może być równa nawet 1 :(

Kiedy? Wtedy gdy liczba jest potęgą dwójki, ale taka liczba nie może być pierwsza

Napisałem na początek coś takiego:

program super_B_pierwsze;
var t:array[1..49999] of boolean;

procedure sito;
var i,j:longint;
begin
 for i:=1 to 49999 do t[i]:=TRUE;
 for i:=1 to 25000 do if t[i] then begin
  for j:=1 to (49999 div (2*i+1)) do t[i+(2*i+1)*j]:=FALSE;
 end;
end;

begin
 sito;
end.

Kompiluje, ale po odpaleniu wyskakuje okienko '16 bit MS_DOS Subsystem' : The NTVDM CPU has encountered an illegal instruction. CS:0000 IP:0075 OP:f0 00 f0 37 05 Choose 'Close' to terminate the aplication., no i pascal się zamyka...

mgr.Dobrowolski napisał(a)

Kiedy? Wtedy gdy liczba jest potęgą dwójki, ale taka liczba nie może być pierwsza

ej racja :D. Ożywiłeś moje nadzieje na duuuzo punktow :D. W sumie nie pomyślałem - ktoś na innym forum mnie przestraszył z tą jedynką...

ale lol będzie jak będę miał 99% :D. Aż się nie mogę doczekać wyników, ciekaw jestem, czy - jak zwykle - nie walnąłem się jeszcze gdzieś ;)