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.
helmut
User
Beiträge: 57
Registriert: Mittwoch 2. November 2005, 07:45
Wohnort: Dormagen

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

@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

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] ]
[url=http://www.leckse.net/artikel/meta/profilieren]Profilieren im Netz leicht gemacht[/url]
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

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

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: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

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

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

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: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

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

Edit: War falsch was ich geschrieben hatte.
Zuletzt geändert von sape am Sonntag 21. Januar 2007, 07:19, insgesamt 2-mal geändert.
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Hier mal mein eben schnell zusammenhackter versuch.

Der Primzahl test ist von Dookie aus diesem Thread: http://www.python-forum.de/post-8344.html#8344

EDIT: Funktionierender Code -> siehe unten.
Zuletzt geändert von sape am Sonntag 21. Januar 2007, 07:09, insgesamt 1-mal geändert.
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Ups, da habe ich einen Fehler gemacht.

Dieser code sollte nun funktionieren.

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import math


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

def make_prims(from_, to):
    return (x for x in xrange(from_, to) if isprim(x))

def get_prim_twins(list_):
    for x in list_:
        for y in list_:
            if x + 2 == y:
                yield x, y
            elif y > x + 2:
                break
                    

if __name__ == "__main__":
    print tuple(get_prim_twins(tuple(make_prims(0, 100))))

Code: Alles auswählen

((1, 3), (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73))
BlackJack

`get_prim_twins()` ist aber nicht besonders effizient, da werden Unmengen an unnötigen vergleichen gemacht.
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Jepp. Und zwar der bereich ``for y in list_:`` ist ineffizient. Es wird immer komplet die Liste durchlaufen, obwohl die "abgearbeiteten" längst irrelevant sind.
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Code: Alles auswählen

def get_prim_twins(list_):
    list2 = list_
    for x in list_:
        for idx, y in enumerate(list2):
            if x + 2 == y:
                yield x, y
                list2 = list2[idx:]
                break
Nun wird in der zweiten for schleife nicht die liste immer komplett von vorne durchgangen, sondern ab dem "letzten" Punkt.


EDIT:
Oder ist die Variante besser von der Lesbarkeit?

Code: Alles auswählen

def get_prim_twins(list_):
    list2 = list_
    for x in list_:
        for idx in xrange(len(list2)):
            if x + 2 == list2[idx]:
                yield x, list2[idx]
                list2 = list2[idx:]
                break
EDIT:

Code: Alles auswählen

def get_prim_twins(list_):
    last_idx = 0
    for x in list_:
        for idx in xrange(len(list_[last_idx:])):
            if x + 2 == list_[last_idx+idx]:
                last_idx += idx
                yield x, list_[last_idx]
                break
:D
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

So einen habe ich noch und dann ist Schluss für heute :D

Code: Alles auswählen

def get_prim_twins(list_):
    last_idx = 0
    return ((x, list_[last_idx+idx]) for x in list_ 
            for idx in xrange(len(list_[last_idx:])) 
            if x + 2 == list_[last_idx+idx])
Ist schön kurz aber ist langsamer, weil immer im zweiten for wider die liste von ganz von voren durchgegangen werden muss ;) Logisch.


BTW: Mit gefällt von den 4 Beispielen, vom Leserlichen her, die ``enumerate``-Version. :)
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Hi

Warum denn immer 2 For-Schleifen?
Hab mal folgende Vorschläge, natürlich kann man diese auch ohne Generator schreiben.

Code: Alles auswählen

from itertools import izip
def get_prim_twins2(prims):
    return ((x,x+2) for x in prims if x+2 in prims)

def get_prim_twins3(prims):
    return ((prim,prim+2) for x,prim in enumerate(prims[:-1]) if prims[x+1]==prim+2)

def get_prim_twins4(prims):
    return ((x,y) for x,y in izip(prims, prims[1:]) if x+2 == y)

Gruss
PS: die "is_prim" Funktion ist falsch, 1 ist keine Primzahl ;)
Antworten