[php]Czy podana liczba jest liczbą pierwszą? Opcje

[b_chmura]

Panowie jak napisać skrypt który sprawdza czy podana liczba jest liczbą pierwszą?

[23kulpamens]

ponieważ nie ma skutecznego algorytmu odnajdywania wszystkich liczb pierwszych, najłatwiej chyba będzie jak zrobisz tablicę z pierwszoma kilkunatoma liczbami pierwszymi i sprawdzać czy liczba jest w tej tablicy. Któreś tam z koleii liczby pierwsze są tak duże że nikt ich chyba nie używa, a tych pierwszych pierwszych nie ma tak dużo Poztym obliczanie czy liczba jest pierwsza za każdym razem pożerałoby dużo mocy obliczeniowej

[dr_bonzo]

A jaka jest definicja libczy pierwszej? Jest to taka liczba ktora jest podzielna tylko przez 1 i przez sama siebie, no i oprocz 1ki.

Czyli sprawdzasz po kolei od 2 do N czy liczba N jest podzielna przez jakas inna liczbe. Oczywiscie mozna to zoptymalizowac.

[Ertai]

Jezeli masz podany zakres (gorne ograniczenie tych liczb) to mozesz sprawdzac czy dana liczba dzieli sie przez wszystkie od niej nizsze z reszta wieksza niz 0, jezeli dzieli sie tylko przez 1 z reszta rowna 0 to znaczy, ze masz liczbe pierwsza. (dzielenie z reszta to operacja modulo). Nie jest to oczywiscie najodpowiedniejszy algorytm ani najszybszy ale jest bardzo prosty do napisania.

[b_chmura]

[PHP] pobierz, plaintext 
<?php
function liczbapierwsza($int)
{
 
  $czy = true;
  $i = 2;
  while($i < $int)
  {
	if($int % $i == 0)
	{
	  $czy = false;
	}
	$i++;
  }
  return $czy;
}
?>
[PHP] pobierz, plaintext 

nie chciało mi się myśleć

[phpion]

Weź to zoptymalizuj trochę... Masz niepotrzebne przebiegi pętli. Zrób to tak:

[PHP] pobierz, plaintext 
<?php
function liczbapierwsza($int) {
	$i = 2;
 
	while($i < $int) {
		if($int % $i == 0) {
			return false;
		}
 
		$i++;
	}
 
	return true;
}
?>
[PHP] pobierz, plaintext 

[b_chmura]

aż tak duże znaczenie ma jak zwracam false lub true?

[phpion]

Nie jak tylko kiedy. Weźmy np. liczbę 999999. Twój kod wykona 999999 pętli po czym zwróci false. Mój natomiast wykona tylko 2 pętle (dla $i=2 oraz $i=3) i również zwróci false. Dlaczego? Ano dlatego, że Ty zwracasz prawdę/fałsz na końcu, po wykonaniu wszystkich pętli, natomiast u mnie zwracany jest fałsz przy pierwszym przypadku spełniającym dany warunek. Podobny efekt uzyskałbyś dając przy spełnieniu warunku instrukcję break; lub dodając do while'a && $czy === true.

Ten post edytował phpion.com 6.11.2007, 20:28:11

[drPayton]

Jeszcze prościej:

[PHP] pobierz, plaintext 
<?php
function is_prime($number)
{
	foreach(range(2, $number-1) AS $test) {
		if($number%$test==0) {
			return false;
		}
	}
	return true;
}
 
 
echo (is_prime(29)) ? "liczba pierwsza" : "liczba nie jest pierwsza";
?>
[PHP] pobierz, plaintext 

[phpion]

Prościej ale czy wydajniej? foreach + range? nie sądzę
PS: aczkolwiek różnice wydajnościowe będą mikroskopijne ale jednak

Ten post edytował phpion.com 6.11.2007, 20:33:09

[Gonzo44]

1. Jeżeli dobrze pamiętam to nie trzeba dzielić przez wszystkie liczby od 2 do N-1, wystarczy do N/2 lub do (N-1)/2, z zaokrągleniem do całkowitych oczywiście.
2. Jeżeli coś nie jest podzielne przez 2 to nie jest też przez jej potęgi, to samo z 3, 5, 7...

[cornholio666]

Witam,

ja jeszcze dorzucę ciekawy temat:

Sito Eratostenesa

Z powyższego linka:

[PHP] pobierz, plaintext 
<?php
/**
		* tworzy tablice z liczbami pierwszymi
		* @param integer zakres wyszukiwanych liczb pierwszych
		*/
		function pierwsze($zakres){
				if(!is_numeric($zakres)) return array();
				$tablica=array_fill(0, $zakres, true); #wypelniamy tablice wartosciami true
				$tablica[0]=false; # 0 nie jest pierwsza
				$tablica[1]=false; # 1 nie jest pierwsza
				for($i=2; $i<=floor(sqrt($zakres)); ++$i){
						if(!$tablica[$i]) continue;
						$w=$i*$i;
						while($w<=$zakres){
								$tablica[$w]=false;
								$w+=$i;
						}			   
				}
 
				return array_keys($tablica, true); #zwracamy tablice z kluczami, ktore maja wartosc true
 
		}
?>
[PHP] pobierz, plaintext 

Ten post edytował cornholio666 7.11.2007, 09:28:59