Ocena użytkownikóww: ***** / 1
Nadesłany przez _marass_, 10 kwietnia 2011 16:55
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.fermat_1_php.php:
<?php
//Szukalski Marek
//www.algorytm.org
//Test pierwszosci Fermata
//funkcja wykorzystujaca algorytm naiwnego potegowania modularnego
//oblicza wartosc ($x^($y-1)) % $y
//http://www.algorytm.org/algorytmy-arytmetyczne/naiwne-potegowanie-modularne.html
function pot_mod($x,$y){
$z=1;
$x=$x % $y;
for($i=0;$i<$y-1;$i++){
$z = $z * $x;
$z = $z % $y;
}
return $z; //zwraca reszte z dzielenia
}
$k=10; //zadana dokladnosc
$p=1231; //sprawdzana liczba
srand ((double)microtime() * 1000000);
$np=0;
while($k && ($np != 1)){
$a=rand(2,$p-1); //losujemy
if(pot_mod($a,$p) != 1) $np=1; //wywolujemy funkcje i sprawdzamy czy zwrocona wartosc jest rozna od 1
$k--;
}
if($np==0) echo $p.' jest prawdopodobnie pierwsza ';
else echo $p.' nie jest pierwsza ';
?>