Berechnung von Primzahlzwillingen

[sape]

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.

[sape]

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]

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]

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

[sape]

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

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]

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