Primzahlen in Python ausgeben?

Hallo, bin Programmier-Anfänger und stelle mich ziemlich doof an. Im Folgenden ist ein Programm, das Primzahlen generiert. Ich verstehe aber nicht was der Computer mach, auch wenn das Programm sehr einfach ist. Kann mir einer an den Primzahlen "2, 3, 5" konkret erklären, was da ausgerechnet wird?

p=2

while True:

  t=2
    
  while p%t !=0 and t<p:
        
     t= t+1
   
  if t==p:
        
     print p

p=p+1

3 Antworten

sarahj

09.02.2016, 21:18

nun, es dividiert ("p%t") durch alle kleineren Zahlen ("while t<p"), bis eine gefunden wird, bei der Rest == 0 raus kommt (also teilbar ist).
Wenn die Schleife beendet ist, UND dann t == p ist, wurde keine gefunden.
Wurde eine gefunden, so wird die Schleife mit t != p enden.

Also ist p eine Primzahl wenn t==p, und wird ausgegeben.

Das Programm ist allerdings ziemlich dumm geschrieben, und wohl der schlechteste Primzahl-Prüf-Algorithmus, den ich seit langem gesehen habe. Er funktioniert, ist aber höchst ineffizient.

Du kannst Dir ein paar Fragen selbst stellen:

1) welches ist wohl die größte Zahl, die p noch ohne Rest teilen würde? Muss man wirklich t bis p laufen lassen, oder kann man vorher aufhören-? Wenn ja, wo?
2) schon allein das Überspringen aller geraden t reduziert die Anzahl der Prüfungen um die Hälfte. Macht also das Programm doppelt so schnell.
Könntest Du Dir vorstellen, welche Zahlen überhaupt als Teiler zu prüfen sind?
(i.e. angenommen p ist nicht durch t teilbar, macht es dann Sinn, 2*t, 3*t, usw. zu versuchen?)

Machtnix53

09.02.2016, 21:50

Wenn man Modulo von 6 berechnet, muss beispielsweise nur bei 1 und 5 weiter getestet werden, da sie bei 0,2,3,4 durch 2 oder 3 teilbar ist. Für schnelleres Testen von großen Primzahlen kann man auch %30 (6*5) ,%210 (30*7) usw verwenden.

Sinnvoll ist es auch die gefundenen Primzahlen aufzulisten, um sie in Tests wiederzuverwerten.

Schachpapa

09.02.2016, 21:57

Zu 2)

Du willst wahrscheinlich darauf hinaus, dass das Prg. nur Primzahlen als Teiler probieren soll. Dann müsste es aber entweder eine Liste aller Primzahlen führen oder jeweils für die mögl. Teiler prüfen, ob sie prim sind. Dann ist es aber einfacher, durch den nichtprimen Teiler zu teilen, obwohl das Ergebnis schon bei den Teilern des Teilers gefunden wurde.

Am Beispiel: Statt zu prüfen, ob ich mir das Teilen durch 91 sparen kann, weil 91 eventuell nicht prim ist, teile ich einfach und stelle fest "teilt nicht" (wenn vorher schon 7 und 13 nicht teilten).

sarahj

09.02.2016, 22:06

@Schachpapa

wollte eigentlich den Gedanken in Richtung Sieb anstoßen.
Da werden ja auch Vielfache rausgestrichen...

Aber ja; man kann auch eine Liste der PrimZahlen halten
(es reicht eine Tabelle der Primzahlen bis zu einer bestimmten Größe, z.B. aller Primzahlen bis 1000. Die benötigt nur 168 Integer-Plätze und könnte statisch definiert oder dynamisch generiert werden).
Damit spart man schon eine Unmenge Divisionen.

Die macht sich natürlich bei kleinen Zahlen wenig bemerkbar;
aber wie lange dauert folgende Abfrage:

179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137859 isPrime

(an andere Leser: große Primzahlen sind wichtig in kryptographischen Algorithmen)

Machtnix53

10.02.2016, 00:08

@Schachpapa

Einfacher vielleicht, aber viel langsamer, wenn du auch durch nicht-prime Zahlen teilst.

sarahj

10.02.2016, 01:02

@Machtnix53

richtig. es wird natürlich erst bei grossen Zahlen auffällig. Wenn man den 64bit Integer-Bereich verlässt, werden Divisionen von großen Zahlen sehr teuer.

gerlochi

09.02.2016, 20:40

Du könntest zuerst testen ob t modulo t gleich 0 ist und dann nochmal prüfen ob t modulo 1 gleich 0 ist.

PS: Modulo= %

gerlochi

09.02.2016, 20:41

obwohl... das geht nicht. dann solltest du t modulo alle anderen zahlen testen, dann ist es möglicherweise richtig!

weihn8en

09.02.2016, 20:45

willst du ob es eine gewisse Zahl testet, oder dass es z.B. 2,3,5,7,11,13,... ausgibt?

IronDetektiv

Fragesteller

09.02.2016, 21:32

2,3,5,... ausgeben

Hey Leute, Ich bin grade dabei die Anfänge von Python zu lernen, und habe jetzt alle Primzahlen von 1 bis 100.000 ausrechnen lassen. Jetzt möchte ich mir die anzahl der Ergebnisse anzeigen lassen. Ich habe mir die Primzahlen so ausrechnen lassen:

endrange=100000

print("Primzahlen von 1 bis {0:d}: ").format(endrange)

for i in range(2,endrange): teilbar = False for j in range(2,i): if i % j == 0: teilbar = True if teilbar == False: print(i)

Also was muss ich da noch dazuschreiben, dass ich die anzahl der Primzahlen von 1 - 100.000 dazubekomme?

MFG

...zur Frage

Python Primzahlen erraten umschreiben?

Hey ich hab ein Programm zu Primzahlen erraten entworfen. Allerdings gefällt es mir noch nicht so gut. Könnte jemand das ganze etwas eleganter programmieren bzw umschreiben?

def teiler(N):

liste=[]

i = 2

rest = 0

while i < N:

rest = N%i

if rest == 0:

liste.append(i)

i=i+1

else:

i=i+1

return(liste)

print("PRIMZAHLENDETEKTOR")

print()

N=2

while N != 0:

N=int(input("Bitte eine Zahl eingeben (Abbruch mit 0): "))

ergebnis=teiler(N)

if len(ergebnis)==0:

print(N," ist eine Primzahl!")

else:

print(N," ist keine Primzahl!")

...zur Frage

Warum lastet Python meine CPU kaum aus?

Ich habe gerade ein Programm in Python mit Hilfe meiner IDE Pycharm geschrieben, welches überprüft, ob eingegebene Zahlen Primzahlen sind. Jetzt wollte ich das ganze mal mit größeren Primzahlen ausprobieren und habe "188748146801" eingeben. Das Programm rechnet jetzt schon eine ganze Weile, wobei im Task Manager anzezeigt wird, dass meine Hardware quasi nicht beansprucht wird. Warum kann auf Kosten von Leistungsaufwand der Prozess nicht schneller ablaufen? Liegt das daran, dass Python nicht gerade die effizienteste Programmiersprache ist oder limitiert Pycharm die Leistung, die beansprucht wird?

Der Code sieht folgendermaßen aus:

input1 = int(input())
prime = True

for num in range(2,input1):
    if input1 % num == 0:
        prime = False
        break

if prime == True:
    print(input1,"is a prime number")

else:
    print(input1,"is not a prime number")

...zur Frage

Eigenes Passwort in Python "hacken"?

Hallo,

Ich habe hier:

#Variablen zuteilen
passwort = "geheim"
userpw = ""
while userpw != passwort: #Whileschleife 
  print("Passwort: ") 
  userpw = input()


  if userpw == passwort: #If-Verzweigung
      print("Das Passwort ist richtig! ")
      break

...ein ganz einfaches Programm in Python geschrieben, welches dich so lange nach einem Passwort fragt, bis es richtig ist. Nun meine Frage:

Kann man, und wenn ja wie, ein anderes Programm in Python schreiben welches probiert das Passwort zu hacken? Entweder mit einem Dictionary, oder mit Brute-Force. Oder anders?

Danke schonmal:)

...zur Frage

Primzahl in Python?

Hallo,

ich bin noch Anfänger im Programmieren und sitze an einer Aufgabe fest. Das Programm soll mir die Werte True oder False geben, wenn es eine Primzahl ist oder nicht. Ich habe die Aufgabe soweit gelöst, aber bei 2 gibt er mir False heraus.

Ich finde den Fehler nicht. Könnte mir jemand erklären, woran es liegt?

Hier einmal mein Code:

import sys

zahl = int(sys.argv[1])
n = 2

if zahl <= 1:
  print(False)
elif zahl % n == 0:
  while n <= zahl:
    n += 1
    print(False)
else:
  print(True)

...zur Frage

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.

...zur Frage

While Schleife in Python?

Hallo,

ich habe eine Übung zur while-Schleife (in Python), in der ich ein Programm schreiben muss, das den Anwender wiederholt dazu auffordert, einen Wert in Inch einzugeben. Der eingegebene Wert soll anschließend in Zentimeter umgerechnet und ausgegeben werden. Das Programm soll nach der Eingabe des Werts 0 beendet werden.

Ihr könnt ja mal meinen Code kopieren und selber sehen was passiert, ist glaube ich einfacher, als wenn ich es erkläre.

#Zuteilung
print("Geben Sie einen Inch-Wert ein: ")
inchwert = input()
eingabe = int(inchwert)

#While-Schleife
while eingabe != 0:
  print("Geben Sie einen Inch-Wert ein: ")
  inchwert = input()
  eingabe = int(inchwert)

  if eingabe != 0:
    print(eingabe, " inch, sind: ", eingabe*2,54, "cm")

  elif eingabe == 0:
    print("Eingabe darf nicht gleich 0 sein")
    break

Meine Frage: Wie mache ich, dass das Programm richtig läuft (Ich meine, dass ich am Anfang des Programms etwas falsch habe), und zweitens: Habe ich die while-Schleife hier richtig in Verwendung?

Danke für jede Hilfe :)

...zur Frage

Python, Sieb des Eratosthenes?

Hallo,

ich schreibe morgen eine Klausur über einige Python Dinge. Könnte mir jemand sagen, was genau ich falsch gemacht habe? Ich habe versucht in Python die Primzahlen von 1-20 auszugeben (Sieb des Eratosthenes), komme aber nicht weiter.

Danke

Liste = [1,20]
Primzahlen = [1,2,5,8]
Liste[1] = 0
Liste[0] = 0
for z in Liste:
  for Liste in Primzahlen:
    if Liste == 0:
      for i in range(2*Liste,20,x):
        Liste[i] = 0
print(z)

...zur Frage

Primzahlen mit Java?

Hey Leute,

Ich würde gerne ein Programm in Java (BlueJ) schreiben, welches mit Hilfe von for und If (kein while!) die Zahlen von 1-100 nach Primzahlen prüft und die Primzahlen ausgibt.

Wie macht man das?

Danke im Voraus ;)

...zur Frage

einfaches Caesar-Chiffre Programm in Python?

Hallo,

Ich habe versucht ein einfaches Caesar-Chiffre-Programm in Python zu schreiben

bisher bin ich soweit gekommen:

import string

def listAlphabet():
  return list(string.ascii_uppercase)

def crypt():
    klartext = str(input("Hier Text/Wort zur Verschlüsselung eingeben: "))
    klartext = klartext.upper()
    i = len(klartext)
    schluessel = int(input("Um wie viele stellen soll verschoben werden? "))
    for i in range(i):
        if klartext[0] == " ":
            print(" ")
            i += 1

        else:
            hashed = klartext[0] - listAlphabet([schluessel])
            print(hashed)
            i += 1

go = True
while go:
    listAlphabet()
    crypt()

Ich will keinen Code, sondern nur wissen, ob ich in irgendeiner Form auf dem richtigen Weg bin, oder wie ich konkret an die Sache rangehen soll

Danke

...zur Frage

Weiter schreiben Python?

Ich möchte das Programm schließen, nachdem ich (no) gedrückt habe

Ich möchte das Programm abschließen, nachdem ich auf (yes) geklickt habe

phoneList = {"name": ["Amal", "Mohammed","Khadijah", "Abdullah", "Rawan", "Faisal", "Layla"], "num": [1111111111, 2222222222, 3333333333, 4444444444, 5555555555, 6666666666, 7777777777]}

while True:

phoneNumber = int(input("Enter phone number: "))

if phoneNumber in phoneList["num"]:

i = phoneList["num"].index(phoneNumber)

print(phoneList['name'][i])

else:

print("This is invalid number")

...zur Frage

Wie programmier ich eine schleife in python, die bei einer bestimmten Zahl aufhört?

Ich brauche eine schleife die bei einer bestimmten Zahl aufhört. Soweit so gut. Nun habe ich aber mehrere if verkettungen und an jedem ende eines if-befehls muss die eine Abfrage kommen, mit welcher man das programm wieder beenden kann.

x = input

while x != 99:

if ...

elif.......

...zur Frage

Python Frage zu While Schleife bzw. zu try / except?

Hallo.

Ich habe gerade eine kleine Denkblockade.

Ich möchte eine Programm immer wieder von vorne starten bis ich mit einer Eingabe das Programm beende. Das funktioniert mir auch Grundsätzlich mit der While Schleife.

Was mir nicht funktioniert ist das es in den Except-Block springt sobald im Try-Block was schief gelaufen ist.

Hab versucht das mit einem einfachem Code darzustellen:

if __name__ == '__main__':
    while_option = True
    while while_option:
        option = int(input('1, 2 oder 3'))
        try:
            if option == 1:
                print("option 1")
                a = int(input('Gib eine Zahl ein!'))
            elif option == 2:
                print("option 2")
            elif option == 3:
                print("option 3 ist beenden")
                while_option = False

        except BaseException as err:
            print("except / BaseException" + err)
        except ValueError as err:
            print("except / ValueError" + err)
        except:
            print('einfach except')

Zur Erklärung:

Bei Programm Start kommt die Frage 1, 2 oder 3. Bei 1 und 2 startet es von vorne und bei 3 wird es beendet. Soweit so gut und auch gewünscht.

Nur ich dachte jetzt wenn in der Variable a was falsches eingegeben wird dass ich das mit einem except abfangen kann, aber dem ist nicht so.

Was verstehe ich da falsch?

Bzw. Wie könnte man dann so einen Fehler abfangen?

Vielen Dank im Voraus

...zur Frage

python function while schleifen Problem?

def test():
  x = None
  while x != "False" or "True":
    x = input("True or False: ")
  for i in x:
    print("It is ")
    print(x, end="")
test()

Wieso funktioniert dieser Code nicht, das Problem liegt darin das man nicht mehr aus der while Schleife raus kommt.

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen