liczny pierwsze

spider865 · Post autor: **spider865** » 17 gru 2008, o 17:35

witam,
szukam dowodu poprawnosci tego algorytmu sprawdzania czy to jest liczba pierwsza

prime(n)
q:=2; Wynik:=true;
while (q< n and Wynik) do
begin
if n mod q=0 then Wynik:=false;
q := q + 1;
end;
if Wynik then "Liczba pierwza" 
else "liczba nie jest l. pierwszą"

Używaj tagów

Kod: Zaznacz cały

.
luka52[/color]

meninio · Post autor: **meninio** » 17 gru 2008, o 18:20

Jeśli chcesz taką metodą badać czy liczba \(\displaystyle{ n}\) jest pierwsza dzieląc ją przez wszystkie liczby naturalne do \(\displaystyle{ n-1}\) i badając resztę z dzielenia to nie musisz sprawdzać podzielności do \(\displaystyle{ n-1}\) tylko wystarczy do \(\displaystyle{ \left[ \sqrt{n} \right]}\), wtedy twój algorytm będzie wykonywał mniej kroków, a więc będzie szybszy.

spider865 · Post autor: **spider865** » 17 gru 2008, o 18:44

ja wiem, że lepiej by było sprawdzać do sqrt(n), ale dostalem takie zadanie, ze mam udowodnić poprawność powyższego algorytmu(taki jak kod powyzej), ale nie mam pojęcia jak

meninio · Post autor: **meninio** » 17 gru 2008, o 19:17

weź se wprowadź jakąś liczbę pierwszą i sprawdź czy algorytm działa....

spider865 · Post autor: **spider865** » 17 gru 2008, o 19:20

to ma być "dowód matematyczny"

meninio · Post autor: **meninio** » 17 gru 2008, o 19:31

Wg mnie tu nie ma co udowadniać, ty po prostu w postaci algorytmu zapisałeś definicję liczby pierwszej. Tak ci ten algorytm trochę lepiej napiszę

Kod: Zaznacz cały

pierwsza:=true;
for(int i=2;i<n;i++)
 if( n % i ==0) {
    pierwsza:=false;
    break;}

if(pierwsza==true) cout<<"Liczba jest pierwsza"; else cout<<"Liczba jest złożona";

spider865 · Post autor: **spider865** » 17 gru 2008, o 19:33

hehe, no ja tez nie widze sensu w udowadnianiu, ale potrzebne mi to na przedmiot algorytmy i struktury danych, a dowod ma byc przeprowadzony "metamtycznie" tzn za pomoca indukcji, z twierdzenia o niezmiennikach petli itp