Berechnung von Primzahlzwillingen

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.
Benutzeravatar
sunmountain
User
Beiträge: 89
Registriert: Montag 13. März 2006, 17:18

Mehr Hilfe gibt es nicht ...

Beitragvon sunmountain » Freitag 12. Januar 2007, 00:09

Code: Alles auswählen

def sieb_des_eratosthenes(min,max):
    zahlen = range(min,max)
    for i in xrange(2,max):
        entferne_vielfache(i,zahlen)
    return zahlen

def entferne_vielfache(i,zahlen):
    for j in xrange(i**2,zahlen[-1],i):
        if j in zahlen:
            zahlen.remove(j)
    return zahlen

MIN=10
MAX=20

primzahlen = sieb_des_eratosthenes(MIN,MAX)

primepaare = [ (primzahlen[i],primzahlen[i+1]) for i in xrange(len(primzahlen)-1) if primzahlen[i]+2==primzahlen[i+1] ]

print "Primepaare von %i bis %i" % (MIN,MAX)
for p in primepaare:
    print p[0]
    print p[1]
    print


Ich denke der Code ist so einfach,
das ich mir Kommentare spare.
[/code]
Benutzeravatar
Luzandro
User
Beiträge: 87
Registriert: Freitag 21. April 2006, 17:03

Beitragvon Luzandro » Freitag 12. Januar 2007, 08:48

Cthulhu hat geschrieben:ich möchte jetzt bitte hilfe zu meinem quelltext haben und nicht wieder auf das sieb des was weiß ich was abgelenkt werden!


Und darf ich dich dennoch mit der Frage nach dem Grund nerven? Dein Code ist höchst umständlich und schwer verständlich geschrieben, weshalb du ja auch selber nicht weißt, was er richtig oder falsch tut. Die Hinweise sollten keine "Ablenkung" sein, sondern dich auf einen sinnvolleren und einfacheren Weg bringen :roll:

@sunmountain
Du gehst hier bei der ersten Funktion ALLE Werte von 2 bis max durch, obwohl ein Großteil davon selbst schon Vielfache von Primzahlen sein werden.

Code: Alles auswählen

def primzahl_zwillinge(a,b):
        bereich = range(2,b)
        primzahlen = []
        while len(bereich) > 0:
                primzahl = bereich.pop(0)
                primzahlen.append(primzahl)
                bereich = [ zahl for zahl in bereich if zahl % primzahl != 0 ]
        return [ (x,y) for x in primzahlen for y in primzahlen if x >= a and x+2 == y ]

Auch nicht optimal, weil die Listcomprehension am Ende im Gegensatz zu deinem Code unnötigerweise 2 Loops enthält, aber ich finde es lest sich so irgendwie schön funktional...

edit:
wobei sich folgendes auch nicht schlechter liest ;)

Code: Alles auswählen

[ (x,x+2) for x in primzahlen if x >= a and x+2 in primzahlen ]
Benutzeravatar
sunmountain
User
Beiträge: 89
Registriert: Montag 13. März 2006, 17:18

3 Experten ...

Beitragvon sunmountain » Freitag 12. Januar 2007, 09:17

... 4 Meinungen :D .
Ich denke mal, jeder hat seine Vorlieben beim Codieren.
Ich bevorzuge den Weg, mir Gedanken über Redudanzen zu machen
wenn Sie die Lesbarkeit beeinträchtigen oder das Laufzeitverhalten.
Solange die Aufgabe nicht lautet, die Primzahlen von 1 bis 1E10 zu suchen,
sollte jede halbwegs "normal" programmierte Version in endlicher
Zeit zu den Ergebnissen kommen.
Benutzeravatar
Luzandro
User
Beiträge: 87
Registriert: Freitag 21. April 2006, 17:03

Beitragvon Luzandro » Freitag 12. Januar 2007, 09:24

Ja schon klar - wollts nur erwähnen, v.a. auch weil ja die Idee vom Sieb darauf beruht, dass man die Vielfachen der Primzahlen entfernt (und ich es irgendwie witzig finde, dass du dann trotzdem xrange verwendest ;) )
Benutzeravatar
sunmountain
User
Beiträge: 89
Registriert: Montag 13. März 2006, 17:18

Wirklich bitter

Beitragvon sunmountain » Freitag 12. Januar 2007, 09:49

fand ich allerdings die Tatsache, das der junge Freund den Hinweisen
der anderen auf die wikipedia nicht gefolgt ist - dort gibt es ein gut leserliches Pascal Programm, das man leicht portieren kann.
(So hab' ich es dann gemacht :oops: ...)
Wer lesen kann ist klar im Vorteil ...
helmut
User
Beiträge: 57
Registriert: Mittwoch 2. November 2005, 07:45
Wohnort: Dormagen

Beitragvon helmut » Freitag 12. Januar 2007, 12:09

Hallo Cthulhu,
wenn Du unbedingt den/die Fehler in deinem Code haben möchtest, dann such sie. Als Hilfe für die Suche habe ich Deinen Code so mit einigen "print"-Anweisungen ergänzt, dass Du schrittweise den Ablauf des Programmes verfolgen kannst. Setze beim Suchen kreuz und quer gerade und ungerade Zahlen für die Grenzen ein. Sieh auch mal in die Dokumentation zur Funktion "range(von, bis, schritt)".


Code: Alles auswählen

#Primzahlzwillinge
print "Um alle Priemzahlzwillinge in einem bestimmten Bereich rauszufinden, bitte den Bereich Definieren:"
a = input("Von: ")
b = input("  bis: ")
for p in range(a,b):
    indent = ""
    print "In for-Schleife. Laufvariable p = %i" % p
    i=1
    j=1
    h=p/2
    print "vor 1. while-Schleife"
    print "Werte: i = %i, j = %i, h = %i" % (i,j,h)
    while j!=0 and i<h:
        indent = "    "
        print indent,"in 1. while-Schleife"
        print indent,"Werte vor Anweisungsblock: i = %i, j = %i, h = %i" % (i, j, h)
        i=i+1
        j=p%i
        print indent,"Werte nach Anweisungsblock: i = %i, j = %i, h = %i" % (i, j, h)
        dummy = raw_input()
    indent = ""
    print "\nNach Durchlaufen/Ueberspringen der 1. while-Schleife"
    print "Vor Pruefung 'if j!=0 and p!=a and p!=1:'"
    print "Werte vor if: j = %i, p = %i, a = %i" % (j, p, a)
    if j!=0 and p!=a and p!=1:
        indent = "    "
        print indent,"Werte vor Anweisungsblock: p = %i" % (p)
        z=p
        print indent, "z = %i" % z
        t=1
        print "t = %i" % i
        k=z+2
        print "k = %i" % z
        print indent, "Werte nach Anweisungsblock: z = %i, p = %i, t = %i, k = %i" % (z, p, t, k)
        print indent, "vor 2. while-Schleife"
        print indent, "Werte: t = %i, i = %i" % (t,i),"\n"
        while t!=0 and i!=h+2:
            indent = "        "
            print indent,"in 2. while-Schleife"
            print indent,"Werte vor Anweisungsblock: i = %i, t = %i, k = %i" % (i, t, k)
            i=i+1
            t=k%i
            print indent,"Werte nach Anweisungsblock: i = %i, t = %i," % (i, t)
            dummy = raw_input
        indent = "    "
        print indent, "\nNach Durchlaufen/Ueberspringen der 2. while-Schleife"
        print indent,"Werte : t = %i, k = %i, a = %i, p = %i" % (t, k, a, p)
        if t>0 and k!=a and p!=1:
            print "\n****************"
            print p
            print k
            print "****************\n"
            dummy = raw_input

Viel Erfolg, Helmut
BlackJack

Beitragvon BlackJack » Freitag 12. Januar 2007, 20:20

@sunmointain: Das `remove()` ist unschön. Damit müssen ziemlich viele Werte unnötig in der Gegend herum kopiert werden.

Luzandro hat geschrieben:

Code: Alles auswählen

def primzahl_zwillinge(a,b):
        bereich = range(2,b)
        primzahlen = []
        while len(bereich) > 0:
                primzahl = bereich.pop(0)
                primzahlen.append(primzahl)
                bereich = [ zahl for zahl in bereich if zahl % primzahl != 0 ]
        return [ (x,y) for x in primzahlen for y in primzahlen if x >= a and x+2 == y ]


Hier gibt's ein ähnliches "Problem".

Auch nicht optimal, weil die Listcomprehension am Ende im Gegensatz zu deinem Code unnötigerweise 2 Loops enthält, aber ich finde es lest sich so irgendwie schön funktional...


Das habe ich jetzt als Herausforderung aufgefasst. Schön funktional liest's sich so:

Code: Alles auswählen

from __future__ import division

import math
from itertools import ifilter, islice, izip, tee


def primes(start, end):
    sieve = [True] * end
    sieve[0] = sieve[1] = False
    for number in xrange(2, int(math.sqrt(end))):
        if sieve[number]:
            for not_prime in xrange(2 * number, end, number):
                sieve[not_prime] = False
    for number in xrange(start, end):
        if sieve[number]:
            yield number


def tail(iterable):
    return islice(iterable, 1, None)


def pairing(iterable):
    iterator_a, iterator_b = tee(iterable)
    return izip(iterator_a, tail(iterator_b))


def twin_primes(start, end):
    def is_twin((a, b)):
        return b - a == 2
    return ifilter(is_twin, pairing(primes(start, end)))


def main():
    print list(twin_primes(10, 100))


:-)
Benutzeravatar
Luzandro
User
Beiträge: 87
Registriert: Freitag 21. April 2006, 17:03

Beitragvon Luzandro » Samstag 13. Januar 2007, 08:35

Ich sollte nicht so leichtfertig das Wort "funktional" verwenden :)
Also ich korrigiere: es lest sich so schön wie ausführbarer Pseudocode ;)

Aber wirklich eine wunderschön funktionale und effiziente Methode hier - ich bin sicher Cthulhu wird auch sofort denken, wieso er nicht gleich darauf gekommen ist ;) (ich hab im ersten Moment genauso darauf gestarrt, wie auf Cthulhus Code...)

Was mir noch aufgefallen ist - das Stop beim xrange ist exclusiv, d.h. es würde noch überall ein +1 dazu gehören.

Noch die ausgebesserte "nicht funktionale Lösung" ohne dem Problem ;)

Code: Alles auswählen

def primzahl_zwillinge(a, b):
        stop = b+1
        ist_prim = [True] * stop
        ist_prim[0] = ist_prim[1] = False
        for zahl in xrange(2, int(math.sqrt(b))+1):
                if ist_prim[zahl]:
                        for vielfaches in xrange(zahl * 2, stop, zahl):
                                ist_prim[vielfaches] = False
        return [ (x, x+2) for x in xrange(a, stop-2) if ist_prim[x] and ist_prim[x+2] ]
EyDu
User
Beiträge: 4866
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Beitragvon EyDu » Samstag 13. Januar 2007, 12:43

So richtig funktional liest sich aber noch keine Lösung. Dazu müsste man wenigstens die Primzahlberechnung noch rekursiv machen. Was natürlich den Stack innerhalb von Bruchteilen einer Sekunde vernichtet ;-)

Daher möchte ich doch mal eine lesbare, und semi-funktionale Lösung vorschlagen. Wer will, darf natürlich die letzte Zeile noch in eine eigene Funktion schieben.

Code: Alles auswählen

def twins(a, b):
   r = []
   for i in range(2, b+1):
      for p in r:
         if i % p == 0:
            break
      else:
         r.append(i)
   return filter(lambda (x,y): x+2==y and x>=a, zip(r, r[1:]))
Cthulhu
User
Beiträge: 38
Registriert: Freitag 17. November 2006, 16:00

Beitragvon Cthulhu » Samstag 20. Januar 2007, 13:49

also wie glaube ich schonmal gesagt kommt es nicht sehr gut biem lehrer an wenn ich hier irgendwelhe sachen benutze von denen er selber noch nie was gehört hat und er sicherlich merkt dass ich dass vorgesagt bekommen habe!
ich habe jetzt wie von blackjack empfohlen mal ein bischen verändert!
Aber ein problem bleibt immenroch! Es funktioniert ja alles einwandfrei bis auf die stelle an der das progr. über prüfen soll ob die primzahl +2 auch eine primzahl ist!
und an der stelle bräuchte ich dann hilfe bitte!
hier wieder der quellcode:

Code: Alles auswählen

#Primzahlzwillinge
print"Um alle Priemzahlzwillinge in einem bestimmten Bereich rauszufinden, bitte den Bereich Definieren:"
a=input("Von ")
b=input(" bis ")
for p in range(a,b):
    i=1
    j=1
    h=p/2
    while j!=0 and i<h:
        i=i+1
        j=p%i
    if j!=0 and p!=a and p!=1:
        t=1
        k=p+2
        while t!=0 and i!=h+2:
            i=i+1
            t=k%i
        if t>0 :
            print p
            print k
            print ""


Hoffe dass ich es dann endlich geschafft kriege!
danke
EyDu
User
Beiträge: 4866
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Beitragvon EyDu » Samstag 20. Januar 2007, 15:34

Du gehst das Problem glaube ich von der falschen Seite an. An Stelle zu prüfen, ob die gefundene Primzahl+2 ebenfalls eine Primzahl ist, würde ich mir die letzte Primzahl merken, und dann prüfen, ob die aktuelle Primzahl-2 dieser entspricht.

Ich hoffe mal, dass das so als Denkanstoß genügt.
Gnushi
User
Beiträge: 77
Registriert: Dienstag 12. Dezember 2006, 09:49

Beitragvon Gnushi » Samstag 20. Januar 2007, 17:44

Hallo zusammen!

Hier ist meine Lösung. Die Untergrenze interessierte mich wenig und die Primzahlberechnung erfolgt auch nicht mit dem Sieb:

Code: Alles auswählen

def primzahlen(Grenze = 10):
    """
      Erzeugt eine Liste von Primzahlen.
      Grenze: Integerwert > 2
      return: Liste
    """
    Liste = [2]

    def ist_prim(a):
        """
          a ist eine Primzahl, wenn sie durch keine vorhergehende Primzahl
          teilbar ist
          return: True, wenn a prim, False sonst.
        """
        tmp_ist_prim = True
        for i in Liste:
            if a % i == 0:
                tmp_ist_prim = False
                break
        return tmp_ist_prim

    # Grenze im richtigen Bereich?
    assert(isinstance(Grenze, int))
    assert(Grenze > 2)
    # Alle Primzahlen auflisten
    for Zahl in xrange(3, Grenze + 1):
        if ist_prim(Zahl):
            Liste.append(Zahl)
    return Liste

Primzahlen = primzahlen(100)
Zwillinge = [(x,y) for x in Primzahlen for y in Primzahlen if x + 2 == y]
print Zwillinge


Liebe Grüße

Gnushi
Benutzeravatar
sunmountain
User
Beiträge: 89
Registriert: Montag 13. März 2006, 17:18

Sieb++

Beitragvon sunmountain » Samstag 20. Januar 2007, 19:45

Gnushi hat geschrieben:Hallo zusammen!

Hier ist meine Lösung. Die Untergrenze interessierte mich wenig und die Primzahlberechnung erfolgt auch nicht mit dem Sieb:

Code: Alles auswählen

def primzahlen(Grenze = 10):
    """
      Erzeugt eine Liste von Primzahlen.
      Grenze: Integerwert > 2
      return: Liste
    """
    Liste = [2]

    def ist_prim(a):
        """
          a ist eine Primzahl, wenn sie durch keine vorhergehende Primzahl
          teilbar ist
          return: True, wenn a prim, False sonst.
        """
        tmp_ist_prim = True
        for i in Liste:
            if a % i == 0:
                tmp_ist_prim = False
                break
        return tmp_ist_prim

    # Grenze im richtigen Bereich?
    assert(isinstance(Grenze, int))
    assert(Grenze > 2)
    # Alle Primzahlen auflisten
    for Zahl in xrange(3, Grenze + 1):
        if ist_prim(Zahl):
            Liste.append(Zahl)
    return Liste

Primzahlen = primzahlen(100)
Zwillinge = [(x,y) for x in Primzahlen for y in Primzahlen if x + 2 == y]
print Zwillinge


Liebe Grüße

Gnushi


Naja. die Ähnlichkeit zum Sieb ist aber schon da ...
EyDu
User
Beiträge: 4866
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Beitragvon EyDu » Samstag 20. Januar 2007, 23:32

Den Block:

Code: Alles auswählen

        tmp_ist_prim = True
        for i in Liste:
            if a % i == 0:
                tmp_ist_prim = False
                break
        return tmp_ist_prim



kannst du übrigens noch vereinfachen. Ist halt so ein typsicher "Anfängerfehler".

Code: Alles auswählen

        for i in Liste:
            if a % i == 0:
                return False
        return True
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Beitragvon sape » Sonntag 21. Januar 2007, 01:40

Edit: War falsch was ich geschrieben hatte.
Zuletzt geändert von sape am Sonntag 21. Januar 2007, 07:19, insgesamt 2-mal geändert.

Wer ist online?

Mitglieder in diesem Forum: brainstir