Primzahlzwillingberechnung, Problem bei der Einschränkung der Wertemenge

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.
Alfons Mittelmeyer
User
Beiträge: 1715
Registriert: Freitag 31. Juli 2015, 13:34

pixewakb hat geschrieben:Eine Endlosdiskussion. Ich denke mittlerweile dürftet ihr den Thread-Starter vertrieben haben. :D
Wird wohl so sein, es geht doch um Hilfestellung für den Threadstarter. Doch bringen einige Beispiele aus Sieb mittels Hy oder wie man das einmal mit Generatoren gemacht hat und diskutiert über continue ja oder nein. Ich stelle nochmals die fertige Lösung für vladima rein, aber vielleicht ist so schon längst vetrieben.

@vladima, wenn Du noch da bist, das wäre die passende Lösung:

Code: Alles auswählen

from math import sqrt

def is_primzahl(wert):

    if wert % 2 == 0:
        return False

    '''Wird der Divisor groesser als die Wurzel,
    dann wird der Quotient kleiner als die Wurzel.
    Daher kann man bereits mit dem groessten ungeradzahligen
    Integerwert vor der Wurzel aufhoeren'''

    reicht_bis = int(sqrt(wert)+0.1) # +0.1 weil auch etwa 16.999999 herauskommen könnte statt 17
    for divisor in range(3, reicht_bis + 2, 2):
        if wert % divisor == 0:
            return False

    return True


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()
Vielleicht läßt man das so stehen, daß sie das sideht und diskutert woanders über continue. Man kann ja einen Thread dazu starten.
BlackJack

@Alfons Mittelmeyer: Bei welchem `sqrt()`-Wert der mathematisch glatt aufgehen würde, käme denn ein Wert heraus der fälschlicherweise abgerundet würde? Und was macht Dich dann so sicher das durch die Addition von 0.1 nicht irgendein Wurzelwert der *tatsächlich* irgendwas.999 ist, fälschlicherweise *aufgerundet* wird?

Zeichenketten sind keine Kommentare und sollten auch nicht dafür missbraucht werden.

Sowohl die Hy-Lösung als auch die Lösung die Generatoren verwendet *sind* Hilfestellungen. Beide lösen die Aufgabenstellung. Beide zeigen wie man Primzahlen generierieren kann, auf zwei verschiedene Arten, die beide effizienter sind als für jeden Kandidaten ohne weitere Information erneut auf Teiler zu prüfen.

Und wenn dann in einer Lösung ein ``continue`` vorkommt, kann man IMHO auch erwähnen wenn man das ein bisschen problematisch sieht. Der Threadstarter könnte das ja auch irgendwo in seiner Lösung in Betracht gezogen haben, oder irgendwann in der Zukunft bei einem anderen Programm tun. Ist wohl zielführender als Bilder von einem Sinclair Heimrechner. :-)
Alfons Mittelmeyer
User
Beiträge: 1715
Registriert: Freitag 31. Juli 2015, 13:34

BlackJack hat geschrieben:@Alfons Mittelmeyer: Bei welchem `sqrt()`-Wert der mathematisch glatt aufgehen würde, käme denn ein Wert heraus der fälschlicherweise abgerundet würde?
Das habe ich schon vielfach in anderen Programmiersprachen gesehen, daß sqrt oft nicht glatt aufgeht, wenn es mathematisch glatt aufgehen sollte. Sqrt arbeitet in andern Pragrammiersprachen mit float und geht da oftmals nicht glatt auf. Wenn Python es immer glatt macht, wäre schön, aber sicher bin ich mir da nicht.
BlackJack hat geschrieben:Und was macht Dich dann so sicher das durch die Addition von 0.1 nicht irgendein Wurzelwert der *tatsächlich* irgendwas.999 ist, fälschlicherweise *aufgerundet* wird?
Ich nehme sogar an, daß da auch aufgerundet werden könnte, Aber was machts, wenn einmal mehr geteilt wird als nötig? Zuwenig aber wäre ein Problem.
BlackJack hat geschrieben:Zeichenketten sind keine Kommentare und sollten auch nicht dafür missbraucht werden.
Auch Zeichenketten benutzt man in Python für Kommentare, das findet man schon in Tutorials für Anfänger, etwa hier: http://www.pythonforbeginners.com/comme ... -in-python

Ob es technisch gesehen auch Kommentare sind oder Strings, die dann, weil nicht zugewiesen in den Garbage Kollektor wandern oder gleich nicht ausgeführt und als Kommentare betrachtet werden, die bin ich allerdings überfragt.
BlackJack hat geschrieben:Sowohl die Hy-Lösung als auch die Lösung die Generatoren verwendet *sind* Hilfestellungen. Beide lösen die Aufgabenstellung. Beide zeigen wie man Primzahlen generierieren kann, auf zwei verschiedene Arten, die beide effizienter sind als für jeden Kandidaten ohne weitere Information erneut auf Teiler zu prüfen.
Das sind keine Hilfestellungen für Anfänger sondern führen nur zur Verwirrung
BlackJack hat geschrieben:Und wenn dann in einer Lösung ein ``continue`` vorkommt, kann man IMHO auch erwähnen wenn man das ein bisschen problematisch sieht. Der Threadstarter könnte das ja auch irgendwo in seiner Lösung in Betracht gezogen haben, oder irgendwann in der Zukunft bei einem anderen Programm tun. Ist wohl zielführender als Bilder von einem Sinclair Heimrechner. :-)
Über continue gibt es verschiedene Meinungen, wenn man darüber eine Diskussion über Vorzüge und Nachteile starten will, dann gehört das in einen eigenen Thread, wo Gegner und Befürworter miteinander streiten können, solange sie wollen. Naja, das mit q.e.d daß man while Schleifen nicht unbedingt braucht, ist wohl ausgeufert bis zum ZX81, der nicht multiplizieren kann auf Maschinenebene. Ja, das hat auch nichts mit dem Primzahlenproblem zu tun.

Aber jetzt hätte man doch endlich damit aufhören können, oder ist das Problem des Threadstartes egal, Haupsache man kann kabbeln?
Benutzeravatar
bwbg
User
Beiträge: 407
Registriert: Mittwoch 23. Januar 2008, 13:35

Alfons Mittelmeyer hat geschrieben:Auch Zeichenketten benutzt man in Python für Kommentare, das findet man schon in Tutorials für Anfänger, etwa hier: http://www.pythonforbeginners.com/comme ... -in-python
Die Aussage in diesem Tutorial ist falsch. Lediglich das erste Beispiel ist ein Kommentar. Das zweite ist ein mehrzeiliges Zeichenkettenliteral. Letzteres wird gerne bei Doc-Strings verwendet, welches Attribut des jeweiligen Objektes wird (__doc__). Kommentare werden im Gegensatz zu Literalen nicht übersetzt.
Alfons Mittelmeyer hat geschrieben:[...] Haupsache man kann kabbeln?
Allerdings. Beim Kabbeln wird man ja gezwungen seinen Standpunkt zu verteidigen und sich mit diesem auseinander zu setzen. Man kann es auch Diskutieren nennen.

Meines Erachtens gehört gerade das Aufzeigen alternative Lösungsansätze in den universitären Kontext. Und gerade Löungen, welche über dem eigenen Niveau liegen, sind bestens geeignet, um dieses anzuheben.
"Du bist der Messias! Und ich muss es wissen, denn ich bin schon einigen gefolgt!"
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@Alfons Mittelmeyer: wenn man nicht weiß, wie floating-point Berechnungen funktionieren, sollte man nicht mal auf gut Glück irgendwelche Werte draufaddieren, und hoffen, dass das dann gut geht. float in Python kann Ganzzahlen bis ungefähr 15 Stellen exakt darstellen und das Ergebnis einer Wurzel ist dann auf so viele Stellen auch exakt. Für größere Zahlen ist dann schon die Darstellung der Quadratzahl nicht mehr exakt und kann dann zu Abweichungen führen die deutlich größer als 0.1 oder 1 oder 10 sind. Sobald Du also float benutzt, bei einem Problem, das eigentlich durch Ganzzahlen lösbar ist, muß Du prüfen, ob Du noch im Gültigkeitsbereich bist, denn sonst bekommst Du unerwarteterweise fehlerhafte Ergebnisse.

Du findest für fast alles im Internet eine irrige Annahme; und schlechte Tutorials gibt es zu Hauf. Da spielt es auch keine Rolle, dass literale Strings als Strings missbraucht keine große Auswirkung auf die Ausführungsgeschwindigkeit haben, es ist einfach ein Fehler.
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

Alfons Mittelmeyer hat geschrieben:Aber jetzt hätte man doch endlich damit aufhören können, oder ist das Problem des Threadstartes egal
Es geht um mehr als nur die Eingangsfrage.

So sieht man an diesem Thread sehr schön, wo die Probleme mit Schutzstellen liegen: Ist der Wert zu klein gewählt, greift er nicht, ist er zu groß, können gleichfalls falsche Resultate die Folge sein. Man sieht zudem wieder einmal, dass man nicht allen "Tutorials" im Netz trauen darf. Und nicht zuletzt sieht man auch ein schönes Beispiel für die Anwendung von Generatoren.

Eine gute Diskussion bietet einen Mehrwert nicht nur für den Fragesteller.
Alfons Mittelmeyer
User
Beiträge: 1715
Registriert: Freitag 31. Juli 2015, 13:34

@vladima: ich habe jetzt berücksichtigt:

- die Funktion is_primzahl soll auch für Werte < 4 funktionieren
- Kommentare schreibt man mit # und nicht mit Stringliteral
- Integerwurzeln, die mathematisch glatt aufgehen, gehen auch in Python glatt auf

Damit sollte das wohl korrekt sein, und ich hoffe auch verständlich:

Code: Alles auswählen

from math import sqrt

def is_primzahl(wert):

    # für negative Werte =======

    assert (wert >= 0),"Wert für Primzahl darf nicht negativ sein"

    # für kleiner 4 ============

    if wert < 4:
        return False if wert < 2 else True

    # ab 4 =====================

    if wert % 2 == 0:
        return False

    # Wird der Divisor groesser als die Wurzel,
    # dann wird der Quotient kleiner als die Wurzel.
    # Daher kann man bereits mit dem groessten ungeradzahligen
    # Integerwert vor der Wurzel aufhoeren

    reicht_bis = int(sqrt(wert))
    for divisor in range(3, reicht_bis + 2, 2):
        if wert % divisor == 0:
            return False

    return True


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()
Benutzeravatar
pixewakb
User
Beiträge: 1408
Registriert: Sonntag 24. April 2011, 19:43

Im Forum gab es m. E. mal eine sehr Performance sieve-Implementierung von Blackjack. Da müsste man m. E. mal die Suche bemühen. Wenn es nicht Hausaufgabe ist, würde ich die Sieb-Implementierung aus sympy nutzen.
jerch
User
Beiträge: 1669
Registriert: Mittwoch 4. März 2009, 14:19

Und wenn man schreibfaul ist, lässt man den Rechner ein bisschen mehr machen:

Code: Alles auswählen

import math

p, f = (
  lambda n, a=3: (False if not n%a else p(n, a+2)) if a+2<math.sqrt(n) else True,
  lambda x, y: ([(x, x+2)] + f(x+2, y) if (p(x) and p(x+2)) else f(x+2, y)) if x+2<y else []
)

print f(600001, 600901)
Alfons Mittelmeyer
User
Beiträge: 1715
Registriert: Freitag 31. Juli 2015, 13:34

Ja, wenn man jedesmal das Paar berechnet, das sind natürlich doppelt soviel Berechnungen, wird der Code kürzer und leichter lesbar:

[codebox=python file=Unbenannt.ps1]def primzahlen_zwillinge(von,bis):
rueckgabe = []
for x in range (von,bis-1): # dann geht x bis bis-2 und x+2 bis bis
if is_primzahl(x) and is_primzahl(x+2):
rueckgabe.append( (x, x+2 ) )
return rueckgabe
[/code]
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@jerch: rekursive Lösungen haben in Python das Problem, dass irgendwann das Rekursionslimit erreicht ist. Es werden floating-point-Berechnungen benötigt, alle Primzahlen doppelt berechnet und ständig neue Listen erzeugt.

Viel effektiver ist

Code: Alles auswählen

from itertools import count, takewhile, chain, izip, islice, tee, imap
p, f = (
  lambda n: all(n%a for a in chain([2], takewhile(lambda x: x*x<n, count(3, 2)))),
  lambda x, y: list((a,a+2) for a,b,c in izip(count(x, 2), *(lambda i,j: (i,islice(j,1, None)))(*tee(imap(p, xrange(x, y, 2)), 2))) if b and c)
)
 
print f(600001, 600901)
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

@Sirius3: schöne Grüße an Larry Wall :)
jerch
User
Beiträge: 1669
Registriert: Mittwoch 4. März 2009, 14:19

@Sirius3: Das ist geschummelt - das hält immer noch Zustände mittels while oder for Schleifen :D
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@jerch: das sind Generatoren. Der einzige Zustand wird durch tee erzeugt.
jerch
User
Beiträge: 1669
Registriert: Mittwoch 4. März 2009, 14:19

@Sirius3: Na dann schau Dir mal, wie die Generation so implementiert sind ;)
BlackJack

@jerch: Das sind Implementierungsdetails. Sonst könnte man jetzt auch den Zustand in der Implementierung von rekursiven Aufrufen anführen. :-)
Üpsilon
User
Beiträge: 222
Registriert: Samstag 15. September 2012, 19:23

Prolog:
[codebox=prolog file=Unbenannt.txt]% sieb(Grenze, Primzahlen)
sieb(2, [2]):-!.
sieb(N, R) :- M is N-1,
sieb(M, R),
member(P, R),
(N mod P) =:= 0,
!. % Dieser Cut ist von eminenter Wichtigkeit!
sieb(N, [N|R]) :- M is N-1, sieb(M, R).

% zwillinge(untere Grenze, obere Grenze, kleinerer Zwilling, gr. Zw.)
zwillinge(U, O, X, Y) :- sieb(O, P),
member(X, P),
X >= U,
Y is X+2,
member(Y, P).
[/code]
zwillinge(0, 50, X, Y)
X = 41,
Y = 43
X = 29,
Y = 31
X = 17,
Y = 19
X = 11,
Y = 13
X = 5,
Y = 7
X = 3,
Y = 5
PS: Die angebotene Summe ist beachtlich.
BlackJack

Da der C64 und Assembler erwähnt wurden, konnte ich nicht anders als das für diesen Rechner in Assembler zu implementieren: Twin Primes between 10102 and 10901 :-D
Antworten