Primzahlzwillingberechnung, Problem bei der Einschränkung der Wertemenge

[vladima]

Hallo ihr Lieben,

ich muss für die Uni ein Programm schreiben, das mir alle Primzahlzwillinge zwischen 10101 und 10901 ausgibt. Das Programm steht, allerdings ist mir nicht klar, wie ich das auf diesen Zahlenraum beschränken kann? Weiß auch nicht so recht, wie ich das googlen könnte und bin gerade (mal wieder..) etwas aufgeschmissen.

Code: Alles auswählen

x = int(input("x = "))
teiler = 2

while teiler < x:
        if x % teiler == 0:
            print (x, "ist keine Primzahl")

            break
        else:
            teiler +=1
            print (x, "ist eine Primzahl")

            if (x+2) % teiler == 0:
                (print (x, "hat keinen Primzahlzwilling"))
            else:
                teiler +=1
                n = x+2
                print (x, "und", n, "sind Primzahlzwillinge")
            break

Ich hab überlegt, das mit einer Liste zu machen, aber das klappt nicht, da ich ja in meiner whileschleife ein x benutze und er aus der Liste kein x nehmen möchte. Versteht ihr was ich meine? Es ist mir auch total peinlich, aber langsam weiß ich echt nicht weiter.

Liebe Grüße,
Laura

[nezzcarth]

Das Programm steht, [...]

Leider nicht, da für dein Programm aktuell zum Beispiel auch 15 eine Primzahl ist, da effektiv nur geprüft wird, ob die Zahl durch Zwei teilbar ist. Die Schleife ist so angelegt, dass sie nur ein einziges mal durchlaufen werden kann und dann in jedem Fall per 'break' unterbrochen wird. Bei dem Verfahren, das du gewählt hast, musst aber mehr als nur eine Zahl prüfen. Für die systematische Berechnung der Primzahlen bis zu einem bestimmten Bereich wird auch gerne ein Sieb-Verfahren verwendet.

[pixewakb]

Google mal "Sieb des Eratosthenes", dann siebst Du und dann gibst Du die Primzahlen im gesuchten Bereich aus der Ergebnisliste aus. Es gibt m. E. auch andere (Sieb-)Verfahren.

Du kennst http://www.sympy.org/en/index.html ???

Dann z. B. http://docs.sympy.org/dev/modules/ntheory.html

Das würde Dir die Arbeit abnehmen, falls das keine Aufgabe/Übung ist, die Du erledigen musst.

[pixewakb]

Es gibt ein "Problem" bei range in Python und zwar ist die erste Zahl dabei und die letzte Zahl ist nicht mehr dabei, d. h. das ist bei sympy analog geregelt, was man berücksichtigen muss, d. h. du müsstest bei der Obergrenze immer +1 rechnen.

Also range(1,5) liefert [1,2,3,4], was man anders erwarten könnte, wenn man mit der Programmierung startet.

Code: Alles auswählen

from sympy import sieve

print([i for i in sieve.primerange(10101, 10901)])

Ergebnis: 10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193, 10211, 10223, 10243, 10247, 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313, 10321, 10331, 10333, 10337, 10343, 10357, 10369, 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459, 10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531, 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639, 10651, 10657, 10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733, 10739, 10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859, 10861, 10867, 10883, 10889, 10891

Code: Alles auswählen

from sympy import sieve

print([i for i in sieve.primerange(1, 11)])

Liefert [2, 3, 5, 7] und eben nicht [2, 3, 5, 7, 11], d. h. achte auf range()!

Guten Erfolg.

[Alfons Mittelmeyer]

Hallo Vladima,

Man fängt nicht einfach an Code zu schreiben. Zuerst braucht man eine Idee. Und da googled man auch nicht rum, sondern denkt nacht. Und dabei teilt man das Problem in kleine Schritte und flugs ist es gelöst.

Was brauchen wir? Wir brauchen eine Funktion, die uns sagt, ob etwas eine Primzahl ist. Dafür vergeben wir einen Namen, etwa:

is_primzahl

Damit ist das erste Problem gelöst. Jetzt ist die Aufgabe, einen Primzahl Zwilling zu finden, also zwei Primzahlen, die sich um der Wert 2 unterscheiden.

Wenn wir also eine Primzahl gefunden haben, dann vergessen wir sie nicht einfach, werfen sie also nicht weg, sondern:

wir heben die Primzahl auf

Wenn wir die nächste Primzahl gefunden haben:

dann vergleichen wir, ob die neu gefundene Primzahl um zwei größer ist als die aufgehobene Primzahl

Ist sie das nicht, werfen wir die aufgehobene Primzahl weg

Haben aber ein richtiges Pärchen gefunden:

dann tun wir es in den Sack
in beiden Fällen heben wir wieder die neu gefundene Primzahl auf
Und das tun wir solange, bis wir unsere Zahlenreihe durch sind
Am Ende sehn wir nach, was im Sack drin ist

Also, ist doch ganz einfach. Ob wir am Anfang oder am Ende anfangen ist egal. Wir können auch einmal am Ende beginnen:

print(sack)

Das war doch einfach. und wie soll unser Sack aussehen, damit wir etwas hineintun können? Eine einfache Variable genügt nicht, denn da muss mehr als nur eins rein. Deshalb nehmen wir eine Liste:

sack = []

Und wenn wir Primzahlzwillinge gefunden haben, wie tun wir sie rein, einzeln nacheinander? Nein, natürlich als Pärchen:

sack.append( (aufgehobene_primzahl, neue_primzahl) )

Und wir können jetzt schon mehr formulieren:

Code: Alles auswählen

def main():

    sack = []
    aufgehobene_primzahl = None

    # es war nicht von 10101 bis 10901, sondern dazwischen
    for zu_untersuchender_wert in range (10102,10901): 

        if is_primzahl(zu_untersuchender_wert):
            neue_primzahl = zu_untersuchender_wert

            if aufgehobene_primzahl != None:
                if neue_primzahl == aufgehobene_primzahl + 2:
                    sack.append( (aufgehobene_primzahl, neue_primzahl ) )

            aufgehobene_primzahl = neue_primzahl

    print(sack)

main()

Und wenn Du noch die Funktion is_primzahl dazu schreibst, ist es fertig und Du bekommt folgende elf Zwillinge heraus:

Code: Alles auswählen

[(10139, 10141), (10271, 10273), (10301, 10303), (10331, 10333), (10427, 10429), (10457, 10459), (10499, 10501), (10529, 10531), (10709, 10711), (10859, 10861), (10889, 10891)]

Liebe Vladima, hast Du jetzt verstanden, wie man das macht, nicht mit x-se und ifs und teilen, sondern mit der Idee, wie man es macht, und daß es dann einfach wird, es zu schreiben?

Noch ein Tip für die Funktion is_primzahl:

zuerst durch 2 teilen (modulo %)
dann von 3 bis zur Wurzel (math.sqrt) im Zweierschritt

Und weil das eine Funktion ist, brauchst Du keine verschachtelten ifs und else, sondern kannst einfach mit return False rausspringen

[Alfons Mittelmeyer]

Ich habe da noch einen Denkfehler drin. Denn eines hatte ich nicht bedacht. Es könnten ja auch drei Primzahlen hintereinander kommen. Da darf ich, wenn ich eine zweite um eins größer als die erste bekomme, die erste nocht nicht wegwerfen, sondern muß sie auch noch für den Vergleich mit einer dritten Primzahl aufheben.

Da musst Du dann noch etwas ändern

[Alfons Mittelmeyer]

Hi Vladima,
Habe nochmal nachgedacht, und die vorige Lösung ist doch richtig. Denn es kann gar nicht sein, daß drei Primzahlen nacheinander kommen. Die folgende Zahl wäre nämlich gerade und kann daher gar keine Primzahl sein!

[bwbg]

Ein Primzahlendrilling in der Form (x, x + 2, x + 4) existiert genau für (3, 5, 7). In allen anderen Fällen ist das letzte Element des Triplets durch 3 teilbar, jedoch niemals gerade.

[Alfons Mittelmeyer]

Ein Primzahlendrilling in der Form (x, x + 2, x + 4) existiert genau für (3, 5, 7). In allen anderen Fällen ist das letzte Element des Triplets durch 3 teilbar, jedoch niemals gerade.

Nein das war nicht gemeint, ich dachte an einen Primzahlendrilling in der Form (x, x + 1, x + 2)

Dafür wäre der Algorithmus nicht ausgelegt, aber so einen Drilling kann es ja auch gar nicht geben, denn zwischen x und x+2 ist immer eine gerade Zahl, die daher keine Primzahl sein kann.

PS: spät in der Nacht sollte man es vielleicht lassen, noch etwas zu denken, besonders wenn man in der Nacht zuvor durchgemacht hatte und nicht noch geschlafen hat.

[BlackJack]

Ich hab's mal mit einem Sieb in Hy implementiert :
[codebox=clojure file=Unbenannt.txt]#!/usr/bin/env hy
(import [math [sqrt]])


(defn primes [start end]
(setv sieve (* [True] end))
(assoc sieve 0 False)
(assoc sieve 1 False)
(for [number (range 2 (integer (sqrt end)))]
(when (get sieve number)
(for [not-prime (range (* 2 number) end number)]
(assoc sieve not-prime False))))
(filter (fn [n] (get sieve n)) (range start end)))


(defn pairing [iterable]
(setv [a b] (tee iterable))
(zip a (rest b)))


(defn twin-primes [start end]
(defn is-twin [pair]
(= 2 (- (second pair) (first pair))))
(filter is-twin (pairing (primes start end))))


(defmain [&rest args]
(-> (twin-primes 10102 10901) (list) (print)))
[/code]

[Alfons Mittelmeyer]

@vladima: man sollte natürlich nicht 'sack' schreiben und zudem eine Funktion daraus machen:

Code: Alles auswählen

def primzahlen_zwillinge(von,bis):
 
    rueckgabe = []
    aufgehobene_primzahl = None
 
    for zu_untersuchender_wert in range (von,bis+1):
 
        if is_primzahl(zu_untersuchender_wert):
            neue_primzahl = zu_untersuchender_wert
 
            if aufgehobene_primzahl != None:
                if neue_primzahl == aufgehobene_primzahl + 2:
                    rueckgabe.append( (aufgehobene_primzahl, neue_primzahl ) )
 
            aufgehobene_primzahl = neue_primzahl

    return rueckgabe
 
def main():
    print(primzahlen_zwillinge(10102,10900))
    
 
main()

Es fehlt nur noch Deine Funktion is_primzahl

Auch sehr wichtig: wer gut benennt, weiß worum es geht, darum sind aussgekräftige Namen bersser als a,b,c,d,...x,y,z

[bwbg]

Von mir eine hausaufgabenkompatible Python2-Version. Ich hatte das Ziel, die berechneten Sequenzen als Generatoren zurückzugeben. Die Funktionen sind nicht laufzeitoptimiert.

Definitionen:

1. Eine Zahl aus der Menge der natürlichen Zahlen (ohne 0) ist prim, wenn sie genau zwei Teiler besitzt.
2. Ein Primzahlzwilling ist ein Paar zweier Primzahlen, deren absolute Differenz Zwei beträgt.

Code: Alles auswählen

#!/usr/bin/env python
# encoding: utf-8
from __future__ import print_function
import itertools

def infinite_range():  # -> [Prime]
    """Returns an infinite generator of prime-numbers. """
    primes = [2]
    yield 2
    for x in itertools.count(start=3, step=2):
        if any(not x % p for p in primes): continue
        primes.append(x)
        yield x

def prime_range(start=1, end=None):  # -> [Prime]
    """Returns a generator of prime-numbers within the given interval
    (`start` to `end` [excluding]). """
    for p in infinite_range():
        if (p >= end) if (end is not None) else False: break
        if p >= start: yield p

def twin_primes(start=1, end=None):  # -> [(Prime, Prime)]
    """Returns a generator of twin-primes withing the given interval
    (`start` to `end` [excluding]). """
    xs = prime_range(start, end)
    ys = prime_range(start, end)
    next(ys)  # Make sure the sequence of `ys` is one prime ahead (n + 1)
    for x, y in itertools.izip(xs, ys):
        if y - x == 2: yield (x, y)
        
def main():
    """Program's entry-point. """
    print(list(twin_primes(start=10102, end=10901+1)))
    
if __name__ == '__name__':
    main()

q.e.d.: Man benötigt keine while-Schleifen.

[Alfons Mittelmeyer]

q.e.d.: Man benötigt keine while-Schleifen.

Ja, das stimmt. Genauso wenig braucht man ein "*" wenn es um das Multiplizieren von Plain Integerzahlen geht.
Dafür reichen auch eine for-Schleife und die elementaren Operationen "&", "<<" und "+".

[BlackJack]

@bwbg: Bei `infinite_range()` würde ich vom Namen her nicht erwarten das das Ding *Primzahlen* liefert, sondern einen Alias für `itertools.count()`.

Iiii, ``continue``.

Das mit den ganzen Schlüsselwortargumenten sieht komisch aus.

Die Bedingung in Zeile 19 liest sich nicht wirklich schön. Das wäre einfacher ausgedrückt:

Code: Alles auswählen

if end is not None and p >= end:

Zweimal `prime_range()` aufzurufen führt auch zu zwei `infinite_range()`-Iteratoren und damit zu doppelt Arbeit und Speicherplatz für die Primzahlen. Schau Dir mal meine Hy-Lösung an: das kann man mit `itertools.tee()` vermeiden.

Die ``for``/``yield``-Schleife lässt sich als Generatorausdruck schreiben.

[kbr]

Genauso wenig braucht man ein "*" wenn es um das Multiplizieren von Plain Integerzahlen geht.
Dafür reichen auch eine for-Schleife und die elementaren Operationen "&", "<<" und "+".

Stimmt, ist in Python aber irrelevant:

Code: Alles auswählen

%timeit 16 * 2
100000000 loops, best of 3: 15.2 ns per loop

%timeit 16 << 1
The slowest run took 72.43 times longer than the fastest. This could mean that an intermediate result is being cached.
100000000 loops, best of 3: 15.6 ns per loop

Abgesehen davon, dass Profiling im Nanosekunden-Bereich eher fragwürdig ist.

[Alfons Mittelmeyer]

Abgesehen davon, dass Profiling im Nanosekunden-Bereich eher fragwürdig ist.

Ich habe so etwas schon geschrieben und es ging nicht um Profiling. Es ging vielmehr darum, daß der Zilog Z80 etwa im ZX81 wie auch der MOS Technology 6502 im Commodore C64 keine Befehle zum Multiplizieren und Dividieren hatten.

Python wäre nicht auf einem ZX81 nicht gelaufen, obwohl ich einen hatte mit doppelt soviel RAM wie die Standardversion, nämlich 2 kB. Naja; RAM war damals auch teuer, ein kB RAM in etwa soviel wie ein Kilo Fleisch.

[kbr]

Mit dem ZX81 hatte ich auch das Vergnügen. Ich erinnere mich aber nur noch in schwarz/weiß ...

[bwbg]

Bei `infinite_range()` würde ich vom Namen her nicht erwarten das das Ding *Primzahlen* liefert, sondern einen Alias für `itertools.count()`.

Den Funktionsnamen habe ich geändert. Ohne Kenntnis des Modulnames (hier: prime) verwirrte infinite_range.

Iiii, ``continue``

Hier bin ich mir noch nicht sicher, warum continue einen Ekelreiz auslöst. Dennoch habe ich die Bedingung geändert, da es sich in diesem Fall trefflich ohne break/continue leben lässt.

Das mit den ganzen Schlüsselwortargumenten sieht komisch aus.

Auch hier bin ich mir nicht sicher um das Warum. Bei den importierten Modulen (itertools) habe ich die Schlüsselworte entfernt. Bei den eigenen Definitionen jedoch aufgrund der Klarheit beibehalten.

Die Bedingung in Zeile 19 liest sich nicht wirklich schön. Das wäre einfacher ausgedrückt:

Code: Alles auswählen

if end is not None and p >= end:

Ohne Zweifel ...

Zweimal `prime_range()` aufzurufen führt auch zu zwei `infinite_range()`-Iteratoren und damit zu doppelt Arbeit und Speicherplatz für die Primzahlen. Schau Dir mal meine Hy-Lösung an: das kann man mit `itertools.tee()` vermeiden.

Dass das den Aufwand in beide Richtungen verdoppelt, war mir bewusst. Ich wusste es nur nicht besser. In Hy könnte ich mich grundsätzlich einlesen, der Aufwand erscheint mir gerade etwas zu hoch

Die ``for``/``yield``-Schleife lässt sich als Generatorausdruck schreiben.

Ohne Zweifel ...

Ohne Doc-Strings und Boilerplate:

Code: Alles auswählen

def infinite_primes():  # -> [Prime]
    primes = [2]
    yield 2
    for x in itertools.count(3, 2):
        if not any(not x % p for p in primes):
            primes.append(x)
            yield x

def prime_range(start=1, end=None):  # -> [Prime]
    for p in infinite_primes():
        if end is not None and (p >= end): break
        if p >= start: yield p

def twin_primes(start=1, end=None):  # -> [(Prime, Prime)]
    xs, ys = itertools.tee(prime_range(start, end))
    next(ys)  # Make sure the sequence of `ys` is one prime ahead (n + 1)
    return ((x, y) for x, y in itertools.izip(xs, ys) if y - x == 2)

[BlackJack]

@bwbg: ``continue`` ist ein unbedingter Sprung an den Schleifenanfang den man an der Einrückung nicht sehen kann, also kann man das leicht überlesen und sieht nicht mehr das nachfolgender Code nicht unbedingt ausgeführt werden muss. Wenn man etwas hinzufügen möchte was grundsätzlich am Ende eines Schleifendurchlaufs ausgeführt wird, dann muss man aufpassen das man das nicht einfach nur ans Schleifenende schreibt, weil das ``continue`` das umgeht. Und etwas was ein ``continue`` enthält lässt sich auch nicht so einfach in eine Funktion heraus ziehen. Zudem kommt man fast immer ohne ``continue`` aus ohne das der Code komplizierter wird.

Bei den Schlüsselwortargumenten finde ich es halt komisch das Du die angibst auch wenn die Werte genau in der Reihenfolge sind, also es keinen Unterschied macht wenn man sie weg lässt.

`Hy` ist ja fast nur Python in Lisp-Syntax. Und die Funktionen aus `itertools` sind schon ”eingebaut”. Also `tee`, `filter`, `zip`, und so weiter sind die Python-Funktionen die man kennt. Das lässt sich relativ einfach nach Python übernehmen. Ist halt praktisch um beispielsweise Hausaufgaben zu beantworten ohne tatsächlich etwas zu liefern das 1:1 übernommen werden kann ohne sich damit tatsächlich auseinander zu setzen.

[pixewakb]

Eine Endlosdiskussion. Ich denke mittlerweile dürftet ihr den Thread-Starter vertrieben haben.