Twierdzenie Wilsona i Pascal

xanowron · Post autor: **xanowron** » 19 sty 2009, o 20:54

Muszę przygotować na jutro na informatykę program w Pascalu który sprawdza czy dana liczba jest pierwsza, problem w tym, że muszę wykorzystać Tw. Wilsona. Nie chodzi mi o super rozbudowany kod, tylko podstawa, z Pascala jestem raczej kiepski i mam z tym problem, a wydaje mi się, że w 10-15 linijkach da się to zmieścić. Gdyby ktoś mógłby mi pomóc albo nakierować na jakieś materiały w internecie byłbym bardzo wdzięczny

abc666 · Post autor: **abc666** » 19 sty 2009, o 21:03

A liczby w jakim zakresie mają być?

xanowron · Post autor: **xanowron** » 19 sty 2009, o 21:12

A to istotne? Jeżeli można wyrazić to typem zmiennej to longint (Jestem noga z Pascala więc oszczędź docinek, bo czuje że nie odpowiedziałem nie na temat )

abc666 · Post autor: **abc666** » 19 sty 2009, o 21:24

wiesz, w musisz liczyć silnie liczby \(\displaystyle{ (p-1)}\) wiec szybko się zakres skończy, dlatego pytałem. Jeśli nie masz sprecyzowanego zakresu tzn. że chodzi tylko "idee".

najlepiej napisz sobie funkcje do liczenia silni albo zmodyfikuj sobie tą
potem tylko liczysz \(\displaystyle{ (p-1)!}\) dla danej liczby p i sprawdzasz czy \(\displaystyle{ (p-1)!+1}\) dzieli się przez p

Kod: Zaznacz cały

if silnia(p-1)+1 mod p = 0 then {jest pierwsza} else {nie jest pierwsza}

xanowron · Post autor: **xanowron** » 19 sty 2009, o 21:32

O tym że zakres szybko się skończy nie pomyślałem, ale chodzi o idee, nie znam się ale taki program jest chyba średnio ekonomiczny
Niemniej bardzo dziękuję za pomoc

Przy okazji, jaki jest typ zmiennej który obejmuje największy przedział?

abc666 · Post autor: **abc666** » 19 sty 2009, o 21:59

Xitami · Post autor: **Xitami** » 20 sty 2009, o 13:27

Kod: Zaznacz cały

begin
    readln(p);
    i:=1; s:=i;
    while i<p do begin
        s:=(s * i) mod p;
        i:=i+1
    end;
    if s=p-1 then writeln('jest pierwsza')
end.

Problem jest w pośrednim wynikiem, (s*i) tu może pojawić się nadmiar.
W Turbo maksimum to longint, czyli "p" nie może przekroczyć 46340.
Delphi i FreePascal dają więcej, np. int64 wtedy p<=3037000499, albo qword wtedy p<2^32.
Fragment można zapisać np. tak "s:=(int64(s) * i) mod p", wszystkie zmienne tylu cardinal, longint czy dword.