Funktion zur Primzahlen-Berechnung

[polynux]

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]

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" .

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

[Dookie]

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]

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]

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]

Hi polynux!

das hab ich nicht verstanden. was bedeutet n**.5 ?

n hoch 0.5 bedeutet Quadratwurzel aus n

gruß

mawe

[Milan]

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]

hallo,

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

gruß

polynux

[Dookie]

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]

O.K., danke