Primzahl

[yokmp]

Hallo, mein erster Post hier.

Ich fange gerade mit Python an und habe mir daher eine Primzahlenbestätigungsfunktion geschrieben (nennt man das so?).

Code: Alles auswählen

def isPrime(x):
	div = x*0.6
	cnt = 0
	for i in range(int(div)):
		mod = x%(i+1)
		if i>=2 and mod != 0:
			cnt = cnt+1
			if cnt+2 == int(div):
				print ("Prime!")
				break
		elif i>=2 and mod == 0:
			print ("Regular")
			break

Ausgabe der Konsole:

Code: Alles auswählen

>>> isPrime(1709)
Prime!
>>> isPrime(17094)
Regular

Bei kleinen Zahlen funktioniert es aber bei Größeren bin ich mir nicht sicher (da ja nur 60% der möglichen Teiler untersucht werden).
Kann jemand bestätigen ob das so funktioniert wie es sollte?

[BlackJack]

@yokmp: „Primzahltest“ wäre wohl die gängige Bezeichnung für so eine Funktion.

Da 5x/3 ≥ √x für x∈ℕ gilt, sollten die 60% reichen. Denn man braucht nur bis zur Wurzel testen um sicher zu sein.

Ansonsten weiss ich nicht ob Dein Quelltext grundsätzlich funktioniert, weil er mir zu kompliziert geschrieben ist, um darüber an einem Sonntag nachzudenken.

Vereinfache den mal. Es werden zum Beispiel nicht alle Namen gebraucht, weil `i` und `cnt` sehr abhängig voneinander sind. Dann solltest Du nur abbrechen wenn ein Teiler gefunden wurde. Wenn keiner gefunden wird, dann läuft halt die Schleife durch. Nach der Schleife weisst Du, dass kein Teiler gefunden wurde und die Zahl damit prim sein muss. Hast Du die Funktion auch mit 0, 1, und 2 ausprobiert? Den ”Sonderfall” 2 würde ich am Anfang extra prüfen.

Bei einem Funktionsnamen, der mit `is`… beginnt, erwartet man üblicherweise, dass die Funktion einen Wahrheitswert zurück gibt und keine Textausgaben macht.

[Newcomer]

Also ganz gängig sind ja die verschiedenen siebe, beispielsweise das von atkin oder eratosthenes
Edit: bei flüchtigem drüberschauen sieht es auch nach atkin aus (-: