Python: Primzahlen erkennen?
Ich möchet gerne ein Programm schreiben das Primzahlen erkennen kann wie mach ich das?? ich weiß nur das ich mit der Probedivision arbeiten muss und welche Zahlen von 2 bis n-1 mit Rest teilbar sind.
4 Antworten
Naja, wie prüfst du denn ob eine Zahl X durch eine Zahl zwischen 2 und X-1 teilbar ist?
Um genau zu sein reicht übrigens auch sqrt (x) als Obergrenze.
ich weiß nur das ich mit der Probedivision arbeiten muss und welche Zahlen von 2 bis n-1 mit Rest teilbar sind.
Jein - da gibt es einige ausgeklügeltere Ansätze vor allem bei der Suche nach sehr großen Primzahlen aber als Anfänger-Beispiel ist das so einsetzbar.
for kantidat in range(1, 1000):
is_primz = True
for teiler in range(2, int(kantidat/2)+1):
if kantidat % teiler == 0 and teiler < kantidat:
is_primz = False
break
if is_primz:
print(str(kantidat) + " ist eine Primzahl")
Einige der komplexeren Algorithmen wären zB: https://de.wikipedia.org/wiki/Primzahltest
Da Primzahlen zB in der Kryptografie recht nützlich sind wird natürlich versucht diese möglichst effizient zu ermitteln.
Nimm unseren Algorithmus als Beipsiel - die geraden Zahlen ab 4 können ja per definition keine Primzahlen sein also könnte man diese bei der Prüfung direkt übergehen...
Du musst nur Teiler bis Wurzel(n) prüfen, und da nur - ausser der 2 - ungerade Zahlen.
ich verstehe das noch immer nicht ganz könntest du mir vielleicht eine Code Beispiel zeigen und damit erklären?
Zunächst prüfst du, ob die Zahl durch 2 teilbar ist, am einfachsten mit der Modulo-Funktion. (Alternativ kannst du auch prüfen ob x/2 = floor(x/2) ist).
Dann machst du eine Schleife, die von 3 bis Wurzel(n) in Zweierschritten läuft und die Zahl auf Teilbarkeit prüft.
Sobald ein Teiler gefunden ist, kannst du natürlich abbrechen.
Ich möchet gerne ein Programm schreiben
vs.
könntest du mir vielleicht eine Code Beispiel zeigen
Das widerspricht sich ein wenig, findest du nicht?
Ich habs mal gemacht:
n = int(input("Zahl: "))
for n in range(2, n-1):
if n % 2 == 0:
print("Keine Primzahl")
break
else:
print("Primzahl")
break
und ich bekomm jetzt den Fehler das egal welche zahl dass er bei jeder "keine primzahl" sagt
Weil die Schleife bei 2 beginnt und 2 nunmal restlos durch 2 teilbar ist.
Du weisst schon, was du da machst, oder?
Du liest eine Zahl n ein und gleich darauf setzt du n in der Schleife auf 2.
Die Schleife ist völliger Quatsch. du überprüfst, ob Zahlen von 2 bis n durch 2 teilbar sind!
Du darfst die Zahl, die du eingibst, nicht als Schleifenzähler nutzen. Der Schleifenzähler ist dein jeweilger Teiler, nicht deine eingegebne Zahl.
Lass mich raten: Du überlegst dir nicht, was zu tun ist, sondern versuchst Code-Schnipsel so abzuändern, dass irgendetwas dabei herauskommt, stiimts?
Das ist nicht Programmieren! Du musst algorithmisches Denken lernen!
Um herauszufinden ob eine bestimmte Zahl eine Primzahl ist, kannst du diesen Code verwenden:
n = int(input("Welche Zahl willst du testen? "))
p = 1
prim = True
if n == 1:
prim = False
else:
i = 2
while i <= n - 1:
if n % i == 0:
prim = False
i += 1
if prim:
print(n, "ist eine Primzahl.")
else: print(n, "ist keine Primzahl.")
um dir alle Primzahlen bis zu einer bestimmten Zahl ausgeben zu lassen, kannst du diesen Code verwenden:
n = 1
p = 1
a = int(input("Bis zu welcher Zahl sollen die Primzahlen berechnet werden? "))
while n < a:
prim = True
if n == 1:
prim = False
else:
i = 2
while i <= n - 1:
if n % i == 0:
prim = False
i += 1
if prim == True:
print(p,"-te Primzahl:")
p += 1
print(n)
n += 1
Warum eigentlich?