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
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.
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.
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.
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).
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…
Zapewne się nie da. Cykliczne działania trzeba wykonywać w pętlach
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.
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…
No w sumie, to odpaliłem to teraz i widzę, że jednak nie
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.
