[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.

[piotrooo89]

do miliona... szok no ale jak chcesz... ja mam cos takiego:

[PHP] pobierz, plaintext 
<?php
$limit=1000000;
$test=2;
 
while($test<$limit)
{
	$niee=0;
	$nie=0;
	$podziel=2;
	while($podziel<$test)
	{
		$wynik=$test%$podziel;
		if($wynik==0)
		$nie++;
		$podziel++;
		$niee=$niee+$nie;
	}
	if($niee==0)
	echo $test .' </ br>';
	$test=$test+1;
}
?>
[PHP] pobierz, plaintext 

[ddiceman]

Mozna to uproscic obliczeniowo, bo wystarczy sprawdzac dzielniki od 2 do pierwsiastka z liczby a nie do liczby:
ps. jedynka jak wiadomo liczba pierwsza nie jest (liczba wg definicji to liczba naturalna, ktora ma dokladnie 2 rozne dzielniki naturalne: 1 i siebie)

[PHP] pobierz, plaintext 
<?php
define('ZAKRES', 1000000);
 
$liczby_pierwsze = array();
for($liczba = 2; $liczba < ZAKRES; $liczba++){
	$liczba_moze_byc_pierwsza = true;
	for($dzielnik = 2, $dl = floot(sqrt($liczba)); $dzielnik < $dl; $dzielnik++){
		if($liczba % $dzielnik == 0){
			$liczba_moze_byc_pierwsza = false;
			break;
		}
	}
	if($liczba_moze_byc_pierwsza == true){
		$liczby_pierwsze[] = $liczba;
	}
}
?>
[PHP] pobierz, plaintext 

Ten post edytował ddiceman 31.07.2008, 10:33:34

[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

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