[Python] numeri primi

[Daniele Zambelli]

Il giorno 02 agosto 2011 17:49, matteo <matteo.web73 a gmail.com> ha scritto:

> import math
> def primi(N):
>
>     """ Print first N prime numbers """
>
>     primes=[2]
>     x=3
>     while x<N:
>        valid=True
>        for divi in primes[:int(math.sqrt(x))]:
>           if x%divi==0:
>              valid=False
>              break
>        if valid:
>           primes.append(x)
>        x=x+2
>     return primes
>
> ecco ;) è sempliciotto, ma gia ho pensato a qualcosa per migliorarlo, voi
> che ne pensate?
>
> _______________________________________________
> Python mailing list
> Python a lists.python.it
> http://lists.python.it/mailman/listinfo/python
>
>
Qualche idea:
- non occorre mettere il 2 fin da subito nella lista dei primi dato che poi,
incrementando di 2 ottieni sempre numeri dispari.
- l'istruzione: primes[:int(math.sqrt(x))] costruisce, ogni volta che viene
chiamata, una nuova lista. Dovresti riuscire a far fare il ciclo in questo
modo:  for divi in primes: ...
- sostituire l'operazione % con la funzione divmod può permetterti di
evitare la radice quadrata.
- non dovrebbe neppure essere un grosso problema evitare l'uso della
variabile isvalid.

Io proverei i tempi con questi cambiamenti, per avere ulteriori
miglioramenti bisogna, penso, impostare l'algoritmo in modo diverso
utilizzando le istruzioni di Python di trattamento delle liste.

Prova e facci sapere dei miglioramenti nei tempi

-- 

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/20110803/e48e401e/attachment-0001.html>