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.
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Beitragvon sape » Sonntag 21. Januar 2007, 02:04

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

Beitragvon sape » Sonntag 21. Januar 2007, 07:08

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

Beitragvon BlackJack » Sonntag 21. Januar 2007, 08:32

`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

Beitragvon sape » Sonntag 21. Januar 2007, 09:51

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

Beitragvon sape » Sonntag 21. Januar 2007, 09:58

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

Beitragvon sape » Sonntag 21. Januar 2007, 10:58

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:

Beitragvon rayo » Sonntag 21. Januar 2007, 15:45

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 ;)

Wer ist online?

Mitglieder in diesem Forum: Google [Bot]