[Skaroth]

Hi,

also wie ein paar vielleicht aus dem letzten Thread von mir wissen, habe ich ein Primzahlen Script geschrieben. Jetzt habe ich aber einen Fehler bei der Berechnung festgestellt: Es werden 1, 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 23 ausgeben, obwohl es eigentlich 2, 3, 5, 7, 11, 13, 17, 19, 23 sein sollten.

Hier der Codeteil von meiner Primzahlen Berechnung:

function ist_primzahl($zahl) {
 for ($j=2; $j <= 7358192; $j++){
		if (($zahl % $j) == 0) {
		 if($zahl==$j) {
		 } else {
		  return false;
		 }
		} else {
		  return true;
		}
	} 
}

Für Hilfe wäre ich sehr dankbar

[Floele]

So würde ich es jedenfalls machen. Gibt zwar bestimmt noch effizientere Möglichkeiten, aber so geht es denke ich:

// Alle Primzahlen von 2 bis $max als Array zurückgeben
function primes($max) {
	$primes = array();
	
	for ($i = 2; $i <= $max; ++$i) {
		$isprime = true;
		
		foreach ($primes as $number) {
			if ($i % $number == 0) {
				$isprime = false;
			}
		}
		
		if ($isprime) {
			$primes[] = $i;
		}
	}
	return $primes;
}

// Überprüfen ob eine Zahl eine Primzahl ist
function isprime($primetest) {
	$primes = array();
	
	for ($i = 2; $i <= $primetest; ++$i) {
		$isprime = true;
		
		foreach ($primes as $number) {
			if ($i % $number == 0) {
				$isprime = false;
			}
		}
		
		if ($isprime) {
			$primes[] = $i;
			if ($i == $primetest) {
				return true;
			}
		}
	}
	return false;
}

// kleiner Test
var_dump(isprime(23));

[hasch]

Na Primzahlen sind doch nur durch 1 und sich selbst teilbar... oder nicht?

Willst du alle Primzahlen generieren oder nur eine zufällige oder mehrere zufällige?

[Floele]

Naja, vielleicht poste dich doch besser noch was schnelleres

function isprime($primetest) {
	$maxtest = sqrt($primetest);
	for ($i = 2; $i <= $maxtest; ++$i) {
		if ($primetest % $i == 0) {
			return false;
		}
	}
	return true;
}

[Skaroth]

Danke Floele, jetzt klappts.

Eines verstehe ich jedoch nicht ganz: Warum ziehst du die Quadratwurzel aus der Zahl?

[Floele]

Steht so bei Wikipedia.

[Rika]

@hasch: Primzahlen sind alle natürlichen Zahlen, die genau zwei Teiler haben. 1 ist durch 1 und sich selbst teilbar, aber hat letztendlich doch nur einen Teiler.

Und für größere Zahlen würde ich neben Trivialfaktortest vor allem einen schnellen Fermat-Test, dann Rabin-Miller und dann, je nach Größe der Zahlen, entweder einen Lehmer oder Agrawal laufen lassen. Damit sortierst du sehr schnell sämtliche Komposite aus und musst nur noch die richtig harten Fälle aufwendig testen.

[joki1987]

Moin,
ich brauchte einen ziemlich performanten Prinzahltest für die visualisierung von den ersten 100k Primzahlen, und habe hier eine Varianten die bei größeren Primzahlen deutlich performanter ist.

function isPrim($zahl) {
   
   // Startwerprobleme ausschließen
   if ( $zahl == 1 ) return false;
   if ( $zahl == 2 ) return true;
   if ( $zahl == 3 ) return true;
   if ( $zahl == 4 ) return false;

   // Was wir sowieso schon wissen, brauchen wir nicht prüfen
   if ( substr($zahl, -1) == 0 ) return false;
   if ( substr($zahl, -1) == 2 ) return false;
   if ( substr($zahl, -1) == 4 ) return false;
   if ( substr($zahl, -1) == 5 ) return false;
   if ( substr($zahl, -1) == 6 ) return false;
   if ( substr($zahl, -1) == 8 ) return false;
   
   $til = sqrt($zahl);
   for ($i = 2; $i <= $til; $i++) {
      if ( ($zahl / $i)*100 == round(($zahl / $i)) * 100 ) {
         return false;
      }   
   }
   return true;
}

Falls ich die Tage dazu kommen, schieß ich nen probabilistischen Algorithmus nach, der den hier noch bei weitem schlägt.
Anbei nen Screenshot der ersten zahlen 2-40001 Zahlen (200 / Zeile). Grün = Prim.

Greetz

Dominic

Dieser Beitrag wurde von joki1987 bearbeitet: 27. November 2012 - 23:07

[TO_Webmaster]

Primzahlen berechnen in php