Funktion zur Primzahlen-Berechnung

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
polynux
User
Beiträge: 11
Registriert: Sonntag 9. Mai 2004, 21:03

Samstag 29. Mai 2004, 20:25

hallo python-forum,

wie kann man eine Funktion prim(n) schreiben, die "wahr" ausgibt wenn n eine Primzahl ist und "falsch" ausgibt, wenn es keine Primzahl ist?

Es scheint da mehrere Lösungen zu geben, z.B. mit dem "Sieb des Erastothenes". Wie würdet ihr das lösen?

gruß

polynux
Milan
User
Beiträge: 1078
Registriert: Mittwoch 16. Oktober 2002, 20:52

Samstag 29. Mai 2004, 22:09

polynux hat geschrieben:Es scheint da mehrere Lösungen zu geben, z.B. mit dem "Sieb des Erastothenes". Wie würdet ihr das lösen?
Hi. Das ist richtig, es gibt bestimmt zig Lösungen, nur wie effizient die sind... naja. Wichtig ist auch, ob du nur mit x-beliebiger Wahrscheinlichkeit sagen willst, ob eine Zahl prim ist oder ob du es ganz sicher wissen willst. Sicher sein kann man natürlich nur durch testen, aber auch da gibt es wieder mehr oder weniger effiziente Varianten. Das Sieb würde ich nicht unbedingt nehmen, es ist besser geeignet, alle Primzahlen in einem Intervall zu finden, als zu sagen ob eine bestimmte Zahl prim ist. Weitere Anregungen findest du über die Forensuche mit Stichwort "primzahlen" :wink: .

Hier noch eine ganz einfache Variante für dich:

Code: Alles auswählen

def prim(n):
    if n==2:
        return True
    if ((n%2)==0) or (n==1):
        return False
    for zahl in xrange(3, int((n**.5))+1,2):
        if n % zahl == 0:
            return False
    return True
Zuletzt geändert von Milan am Sonntag 30. Mai 2004, 15:45, insgesamt 2-mal geändert.
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Samstag 29. Mai 2004, 22:41

Hi polynux,

hier mal eine Variante mit dem Sieb

Code: Alles auswählen

import math

def isprim(n):
    plist = [2]
    for i in xrange(3, int(math.sqrt(n))+1,2):
        for j in plist:
            if i % j == 0:
                break
        else:
            plist.append(i)
    for i in plist:
        if n % i == 0:
            return False
    else:
        return True
könnte man auch noch optimieren, wenn die Funktion öfter gebraucht wird in einem Programm, damit nicht jedesmal eine Liste mit Primzahlen erzeugt wird sondern nur einmal und danach nur noch um die fehlenden für den Test ergänzt wird.


Gruß

Dookie
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Samstag 29. Mai 2004, 23:06

hier noch die für Mehrfachaufrufe optimierte version

Code: Alles auswählen

def isprim(n, plist=[2,3]):
    #liste der Primzahlen bis sqrt(n) ergänzen falls nötig
    for i in xrange(plist[-1], int(math.sqrt(n))+1,2):
        for j in plist:
            if i % j == 0:
                break
        else:
            plist.append(i)
   
    # n  testen
    if n in plist:
        return True
    else:
        for i in plist:
            if n % i == 0:
                return False
        else:
            return True 
Gruß

Dookie
polynux
User
Beiträge: 11
Registriert: Sonntag 9. Mai 2004, 21:03

Sonntag 30. Mai 2004, 10:22

O.K., danke für die Antworten.

@Milan

diese Zeile Code musst du mir nochmal genauer erklären:

Code: Alles auswählen

for zahl in xrange(3, int((n**.5))+1,2): 
if n % zahl == 0: 
            return False 
ist xrange das gleiche wie range? Du nimmst da n modulo Zahl. Falls bei dieser der Rest Null ist wird False zurückgegeben, das hab ich verstanden. Nur die Zahl kommt aus einem Bereich von 3 - ?

Code: Alles auswählen

xrange(3, int((n**.5))+1,2)
das hab ich nicht verstanden. was bedeutet n**.5 ?
mawe
Python-Forum Veteran
Beiträge: 1209
Registriert: Montag 29. September 2003, 17:18
Wohnort: Purkersdorf (bei Wien [Austria])

Sonntag 30. Mai 2004, 10:47

Hi polynux!
das hab ich nicht verstanden. was bedeutet n**.5 ?
n hoch 0.5 bedeutet Quadratwurzel aus n

gruß

mawe
Milan
User
Beiträge: 1078
Registriert: Mittwoch 16. Oktober 2002, 20:52

Sonntag 30. Mai 2004, 14:48

Hi. Sagen wir mal xrange ist ähnlich wie range, aber bildet statt einer Liste mit allen Werten nur ein Generatorobjekt. Durch dieses Objekt kann mittels einer for-Schleife iteriert werden, sodass du zum Schluss den selben Effekt in der Schleife hast, nur dass die einzelnen i's oder hier zahl's immer erst neu gebildet werden. Das hat den Vorteil, dass bei großen Intervallen Speicher gespart wird. Von der Geschwindigkeit ist xrange sogar range leicht überlegen, deswegen die Verwendung. Meinen pydo-xrange-code kannst du hier sehen.
Das ich wiederum ab 3 starte zu iterieren liegt auf der Hand: ich gehe in 2er Schritten weiter und habe so optimiert, dass nicht jede gerade Zahl durchgetestet werden muss. Schließlich ist keine Primzahl (außer der 2) gerade. Zusätzlich ist n**.5==math.sqrt(n), wie mawe richtig gesagt hat (bin halt zu faul, math zu importieren) und optimiert die Anzahl der Durchläufe durch die For-Schleife. So kann man z.B. bei 17 schon aufhöhren zu iterieren, wenn man 17%4 getestet hat (man überlege sich das anhand der Primfaktorzerlegungen einer Zahl).
polynux
User
Beiträge: 11
Registriert: Sonntag 9. Mai 2004, 21:03

Sonntag 30. Mai 2004, 17:14

hallo,

danke für die ausführliche Erklärung. :wink: Hab soweit alles verstanden. Nur der Zusammenhang von n**.5 und der Primfaktorzerlegung ist mir noch nicht ganz klar.

gruß

polynux
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Sonntag 30. Mai 2004, 17:58

die Berechnung x**.5 bringt das gleiche Ergebnis wie sqrt(x).
da sqrt(x)*sqrt(x) == x brauchen beim Testen der Teilbarkeit nur Zahlen bis sqrt(x) getestet zu werden. Jeder grössere Teiler, der keinen Rest ergibt, hat als Ergebnis einen Wert der kleiner als sqrt(x) ist und auch keinen Rest bei der Division ergibt.

Gruß

Dookie
polynux
User
Beiträge: 11
Registriert: Sonntag 9. Mai 2004, 21:03

Mittwoch 2. Juni 2004, 15:20

O.K., danke
Antworten