[Python] numeri primi

[Daniele Zambelli]

Scusate se intervengo molto in ritardo, ma propongo un paio di algoritmi
che, hanno tempi paragonabili a quelli migliori, ma risultano molto più
semplici.

Questo cerca di ottimizzare l'algoritmo:

def crivello7(n):

    if n <= 2:

        return []

    c = list(range(3, n, 2))

    top=len(c)

    for primo in c:

        if primo:

            base = (primo*primo - 3) // 2

            if base >= top:

                break

            for j in range(base, top, primo):

                c[j]=0

    return [2] + list(filter(None, c))


Questo usa le capacità di Python:

def sieveOfEratostenes2(n):

    if n <= 2:

        return []

    sieve = list(range(3, n, 2))

    top = len(sieve)

    for si in sieve:

        if si:

            bottom = (si*si - 3) // 2

        if bottom >= top:

            break

        sieve[bottom::si] = [None] * -((bottom - top) // si)

    return [2] + list(filter(None, sieve))


Come il precedente ma usa numpy:

def sieveOfEratostenes3(n):

    if n <= 2:

        return []

    sieve = numpy.arange(3, n, 2, dtype = int)

    top = len(sieve)

    for si in sieve:

        if si:

            bottom = (si*si - 3) // 2

        if bottom >= top:

            break

        sieve[bottom::si] = 0

    return [2] + list(filter(None, sieve))


Sono algoritmi suggeriti, se non sbaglio da Bearophile

Ciao

-- 

Daniele

www.fugamatematica.blogspot.com

    giusto!
    nel verso
    forse è perché non guardiamo le cose
    Quando non ci capiamo,
-------------- parte successiva --------------
Un allegato HTML è stato rimosso...
URL: <http://lists.python.it/pipermail/python/attachments/20110827/66d570b6/attachment.html>