[PHP]Liczby pierwsze Opcje

[Mlodycompany]

Witam. Chciałbym zrobić generator liczb pierwszych do miliona. Liczba pierwsza to ta która dzieli się przez siebie i przez 1 czyli w sumie mam dwa dzielniki. Głowie się nad tym już parę godzin i nic dobrego nie wymyśliłem. Oto co zdołałem zrobić:

[PHP] pobierz, plaintext 
<?php
print('<pre>');
function znajdzDzielniki($liczba){
		$dzielniki = array();
		for($i = 1; $i <= $liczba; $i++){
			$dziel = $liczba % $i;
			if($dziel == 0){
				$dzielniki[] = $i;
			}
		}
		print_r($dzielniki);
}
function znajdzPierwsze($liczba){
		$pierwsze = array();
		for($i = 1; $i <= 1000000; $i++){
			$dziel = $liczba % $i;
			if($dziel == 0){
				echo znajdzDzielniki($i);
			}
		}
		print_r($pierwsze);
}
 
 
echo znajdzPierwsze($_GET['liczba']);
?>
[PHP] pobierz, plaintext 

Czy ktoś mógłby mnie naprowadzić na opracowanie dobrego skryptu?? Proszę o pomoc.

[Shili]

Prawda jest taka, że sprawdzając warto skakać od cyfry 3 co 2. Przy wyłuskiwaniu liczb pierwszych.
Przy sprawdzaniu kolejnych warto na samym początku dać if liczba % 2 == 0, jeśli nie to w pętli również skaczemy od 3 co 2 elementy

Wiadomo, że 4, 14314, 141412412 nie są pierwsze. Na wstępie więc można je odrzucić. A jeśli coś dzieli się przez parzystą liczbę, to dzieli się również przez cyfrę 2, wystarczy więc sprawdzić tylko ten warunek.
Nie chce mi się modyfikować Waszych algorytmów, ale pozwoli to zaoszczędzić może nie tak dużo, ale zawsze trochę czasu (IMG:http://forum.php.pl/style_emoticons/default/winksmiley.jpg)

Ten post edytował Shili 31.07.2008, 11:47:27