algorytm.org

Implementacja w Php



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Test pierwszości - test Fermata - Implementacja w Php
Ocena użytkownikóww: *****  / 1
SłabyŚwietny
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 ';

?>
Dodaj komentarz