[pascal] liczby pierwsze


(Uzikan) #1

Witam, robiłem zadanko domowe na infe i chcę się upewnić że dobrze rozwiązałem problem. Problem choć prosty to jednak do nauki podstaw programowania dobry. Program sprawdza czy liczba N jest liczbą pierwszą. Pisałem go jak widać w Pascalu :stuck_out_tongue:

program pierwsza;

uses Crt;

var

liczba,i:longint;

begin

writeln('Podaj liczbe: ');

readln(liczba);

clrscr;

for i:=2 to liczba-1 do

 if (liczba mod i)=0 then

   begin

   writeln(liczba,' NIE JEST liczba pierwsza');

   break;

   end

 else

   begin

   writeln(liczba, ' JEST liczba pierwsza!');

   break;

   end;

readln;

end.

(rozwalkompa) #2

U mnie, na lekcji korzystaliśmy z takiego programu:

VAR d,k:longint; p:real;

BEGIN

readln(k);

if k<4 then writeln('tak')

else if k=4 then writeln('nie')

 else

  begin

  p:=sqrt(k)+1;

  d:=2;

  while (d
0) DO d:=d+1;

   if (k mod d)=0 then writeln('nie')

   else writeln('tak');

  end;

readln;

END.

(Dashmen515) #3
program liczba_pierwsza;

uses crt;

var

 lp:longint;

begin

 clrscr;

  writeln('Podaj liczbe ');

   read(lp);

    begin

     if lp mod 2 <> 0 then writeln('Liczba nie jest liczba pierwsza')

     else writeln('Liczba jest liczba pierwsza');

    end;

 readln;

end.

stworzyłem go w notatniku na potrzebę chwili, ale nie wiem czy działa.


(somekind) #4

Pierwsze miały być, a nie parzyste. To "mała" różnica. Dokładnie opisana w Wikipedii na przykład.

Moim zdaniem nie powinno być w ogóle tego brake, którego pogrubiłem. Przecież program ma sprawdzić wszystkie dzielniki, a w tej wersji sprawdzi tylko jeden, bo w każdym przypadku (czy się podzieli, czy nie) pętla zostanie przerwana. Równie dobrze mogłoby jej nie być.

Ponadto nie ma sensu dzielić liczby przez wszystkie liczby od niej mniejsze, ponieważ w pewnym momencie zaczniemy sprawdzać ponownie te same liczby. Dlatego lepiej ograniczyć dzielniki do pierwiastka ze sprawdzanej liczby zaokrąglonego w górę.

Np. dla liczby 103 nie ma sensu dzielić przez dzielnik większy niż 11, bo jeśli np. nie podzieliła się przez 5 (dała wynik 20 reszty 3), to i nie podzieli się przez 20 (bo da wynik 5 i reszty 3).

Mam nadzieję, że jasno napisałem :slight_smile:


(Uzikan) #5

OK. Rozumiem. Ale jeśli nie będzie tego drugiego break co pogubiłeś to komunikat wyświetli sie wiecej niż jeden raz prawda? A tego nie chcę.

A poza tym nie wiem jak można rozwiązać to bez pętli... Przecież nie znamy liczby i nie wiemy ile działań (dzieleń) musimy wykonać aby sprawdzić czy liczba jest tylko podzielna przez 1 i samą siebie...


(somekind) #6

Tak, masz rację.

Zapewne się nie da. Cykliczne działania trzeba wykonywać w pętlach :slight_smile:

To ja mam taką propozycję - zrobić sobie zmienną pomocniczą typu logicznego, przelecieć w pętli po wszystkich dzielnikach, jeśli się podzieli bez reszty, to ustawić tą zmienną na false i przerwać pętle. A dopiero później wyświetlić komunikat:

program pierwsza;

uses Crt;

var

liczba,i:longint;

czyPierwsza:boolean;

begin

czyPierwsza:=true;

writeln('Podaj liczbe: ');

readln(liczba);

clrscr;

for i:=2 to liczba-1 do

 if (liczba mod i)=0 then

   begin

   czyPierwsza := false;   

   break;

   end;


 if (czyPierwsza=true)

   begin 

   writeln(liczba, ' JEST liczba pierwsza!');

   end

 else

   begin

   writeln(liczba,' NIE JEST liczba pierwsza');

   end;

readln;

end.

(Uzikan) #7

no ale czy twój sposób różni się w efekcie działania od mojego? Wydaje mi się że oba programy rozwiązują problem...


(Szymonknop) #8

Nie chce mi się czytać powyższych wypowiedzi ale :

Najszybszym sposobem jest sito Euklidesa wykonywane aż do momentu gdy liczba znaleziona przez sito jest większa od N. Jeśli liczba ta jest równa N to ta liczba jest liczbą pierwszą jeśli liczba jest większa od N to N nie jest liczbą pierwszą ... ale mieszam... ale chyba jasne ?

Złączono Posta : 09.12.2007 (Nie) 22:31

oczywiście można jeszcze podzielić N z resztą przez wszystkie liczby k > 1 i k < N/2 + 1 i jeśli wynik jest równy 0 to automatycznie przerwać wykonywanie pętli... w sumie to jest chyba szybsze...


(somekind) #9

No w sumie, to odpaliłem to teraz i widzę, że jednak nie :slight_smile:

Ale można to jeszcze przyspieszyć, zmniejszając zakres działania pętli, żeby zamiast "liczba-1" był pierwiastek kwadratowy z tej liczby zaokrąglony w górę.

Czasem warto, żeby nie pisać urwanych z choinki postów.

Eratostenesa A to, że opiera się ono na dowodzie Euklidesa to nie powód, żeby tych dwóch panów mylić.

Tak żeś zakręcił, że jak ktoś nie wie, o co chodzi z sitem, to po przeczytaniu tego ucieknie. Ten sposób jest bardzo pamięciożerny.