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.
polynux
User
Beiträge: 11
Registriert: Sonntag 9. Mai 2004, 21:03

Funktion zur Primzahlen-Berechnung

Beitragvon polynux » 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

Re: Funktion zur Primzahlen-Berechnung

Beitragvon Milan » 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.
Benutzeravatar
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Beitragvon Dookie » 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
Benutzeravatar
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Beitragvon Dookie » 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

Beitragvon polynux » 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])

Beitragvon mawe » 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

Beitragvon Milan » 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

Beitragvon polynux » 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
Benutzeravatar
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Beitragvon Dookie » 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

Beitragvon polynux » Mittwoch 2. Juni 2004, 15:20

O.K., danke

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]