[Python] numeri primi

ciao a tutti ;) non me ne intendo molto di programmazione, sono alle prime armi, ma secondo voi è buono un codice che riesce in 5 secondi a trovare tutti i numeri primi da 1 a 100? (ho un intel i3 da 3 ghz) P.S.: il codice l'ho elaborato io studiando un po da solo i numeri primi ___

Re: [Python] numeri primi

2011/8/2 matteo > non me ne intendo molto di programmazione, sono alle prime armi, ma secondo > voi è buono un codice che riesce in 5 secondi a trovare tutti i numeri primi > da 1 a 100? (ho un intel i3 da 3 ghz) > in assoluto? dipende :-) marco@aigor:~$ time primes 1 100 > /dev/null

Re: [Python] numeri primi

2011/8/2 matteo > P.S.: il codice l'ho elaborato io studiando un po da solo i numeri primi > forse può interessarti http://stacktrace.it/2008/01/progetto-eulero-problema-3/ ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/l

Re: [Python] numeri primi

2011/8/2 Marco Mariani > 2011/8/2 matteo > > >> non me ne intendo molto di programmazione, sono alle prime armi, ma >> secondo voi è buono un codice che riesce in 5 secondi a trovare tutti i >> numeri primi da 1 a 100? (ho un intel i3 da 3 ghz) >> > > in assoluto? dipende :-) > > marco@aigor

Re: [Python] numeri primi

Il 02/08/2011 17:44, Marco Mariani ha scritto: 2011/8/2 matteo mailto:matteo.we...@gmail.com>> non me ne intendo molto di programmazione, sono alle prime armi, ma secondo voi è buono un codice che riesce in 5 secondi a trovare tutti i numeri primi da 1 a 100? (ho un intel i3 da 3

Re: [Python] numeri primi

senza entrare in merito ai tempi, perche come qualcuno ha detto dipende da quello che fai con i numeri, di solito la print su standard output impiega più tempo del trovare i numeri direi che puoi ottimizzare questa linea 2011/8/2 matteo > for divi in primes[:int(math.sqrt(x))]: ad esempio per

Re: [Python] numeri primi

Il 02/08/2011 18:00, Simone Federici ha scritto: senza entrare in merito ai tempi, perche come qualcuno ha detto dipende da quello che fai con i numeri, di solito la print su standard output impiega più tempo del trovare i numeri direi che puoi ottimizzare questa linea 2011/8/2 matteo mailto:

Re: [Python] numeri primi

Marco Beri wrote: Bravo il mio amico, eh? :-) Chi e'? Lo conosco... A me piace barare: % time python erat_matrix.py 1000 (array([ 2, 3, 5, ..., 971, 973, 991]),) python erat_matrix.py 1000 0.61s user 0.12s system 38% cpu 1.930 total -- . ..: -enrico- _

Re: [Python] numeri primi

Marco Beri writes: > Usando un algoritmo scritto (in Python) da un amico: > timeit.timeit("import km;km.sieve(100)", number=1) > 0.12970614433288574 timeit.timeit("import km;km.sieve(1000)", number=1) > 1.3863430023193359 timeit.timeit("import km;km.sieve(1)", numbe

Re: [Python] numeri primi

Il 02/08/2011 21:15, Mauro Casini ha scritto: Marco Beri writes: Usando un algoritmo scritto (in Python) da un amico: timeit.timeit("import km;km.sieve(100)", number=1) 0.12970614433288574 timeit.timeit("import km;km.sieve(1000)", number=1) 1.3863430023193359 timeit.timeit("impor

Re: [Python] numeri primi

2011/8/2 matteo : > Il 02/08/2011 21:15, Mauro Casini ha scritto: >> Marco Beri  writes: >>> Usando un algoritmo scritto (in Python) da un amico: >> timeit.timeit("import km;km.sieve(100)", number=1) >>> 0.12970614433288574 [...] >> Si può fare di meglio: >> In [25]: timeit.timeit('num.prim

Re: [Python] numeri primi

Carlo Miron wrote: Ha barato;) Rileggi bene il suo mail. Beh, in confronto io *non* ho barato... ;) -- . ..: -enrico- ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python

Re: [Python] numeri primi

2011/8/2 Mauro Casini > > timeit.timeit("import km;km.sieve(100)", number=1) > > 0.12970614433288574 > timeit.timeit("import km;km.sieve(1000)", number=1) > > 1.3863430023193359 > timeit.timeit("import km;km.sieve(1)", number=1) > > 14.972478151321411 > > > In [29

Re: [Python] numeri primi

Il giorno 02 agosto 2011 17:49, matteo ha scritto: > import math > def primi(N): > > """ Print first N prime numbers """ > > primes=[2] > x=3 > while xvalid=True >for divi in primes[:int(math.sqrt(x))]: > if x%divi==0: > valid=False >

Re: [Python] numeri primi

>Enrico Franchi writes: > A me piace barare: > > % time python erat_matrix.py 1000 > (array([ 2, 3, 5, ..., 971, 973, 991]),) > python erat_matrix.py 1000 0.61s user 0.12s system 38% cpu 1.930 total Ho fatto anche di peggio. Programma per trovare il maggior

Re: [Python] numeri primi

Il 03/08/2011 09:15, Mauro Casini ha scritto: >> Enrico Franchi writes: > >> A me piace barare: >> >> % time python erat_matrix.py 1000 >> (array([ 2, 3, 5, ..., 971, 973, 991]),) >> python erat_matrix.py 1000 0.61s user 0.12s system 38% cpu 1.930 total > >

Re: [Python] numeri primi

matteo writes: > come hai fatto :O , io non riesco neanche a migliorare i miei 3,8 > secondi per 100 :/ Ho barato :) Guarda anche la seconda parte del messaggio: la funzione si limita a restituire un generatore, poi i numeri primi verranno calcolati quando si "userà" il generatore. ciao, M

Re: [Python] numeri primi

Valerio De Carolis wrote: % time python erat_matrix.py 1000 > (array([ 2, 3, 5, ..., 971, 973, 991]),) > python erat_matrix.py 1000 0.61s user 0.12s system 38% cpu 1.930 total Ho fatto anche di peggio. Chiaro. Il senso era che di fatto il mio crivello e

Re: [Python] numeri primi

Nel tuo programma hai eliminato in partenza i numeri pari, controllando solo quelli dispari. La stessa cosa si può fare anche per quelli divisibili per 3 controllando solo i numeri del tipo 6k+1 e 6k+5. Ovviamente si può andare avanti eliminando anche i multipli di 5, di 7, ... ogni volta però il

Re: [Python] numeri primi

Il 03/08/2011 09:42, Valerio De Carolis ha scritto: Comunque salvati su file quanto occupano i primi 100 primi?! :D 526kb ;) ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python

Re: [Python] numeri primi

Fabrizio (in cc) sta per mettere tutte le sue librerie aggiornate su Bitbucket [tra parentesi le ha (abbiamo) usate per risolvere un tot di problemi di Project Eulero]. Qui metto solo il suo sieve.py che ritengo uno dei più veloci esistenti, Rabin e/o Miller compresi. Ciao. Marco. -- http://ber

Re: [Python] numeri primi

>> Comunque salvati su file quanto occupano i primi 100 primi?! :D > > 526kb ;) E poi dicono della solitudine dei numeri primi :) Scusate l'OT ma ormai la battuta ci stava. Un paio di considerazioni pero' che mi erano venute in mente empo fa al riguardo sono che oltre a non essere pari (quin

Re: [Python] numeri primi

Il 03/08/2011 10:28, Marco Beri ha scritto: Fabrizio (in cc) sta per mettere tutte le sue librerie aggiornate su Bitbucket [tra parentesi le ha (abbiamo) usate per risolvere un tot di problemi di Project Eulero]. Qui metto solo il suo sieve.py che ritengo uno dei più veloci esistenti, Rabin e

Re: [Python] numeri primi

2011/8/3 matteo wowo marco, è veloce il codice ;) è circa 100 volte piu veloce del mio :O > (circa 5 secondi per i primi fino a 100.000.000), comunque ho un problemino > con il timeit :/ > Fabrizio è un mito. > >>>timeit.timeit("from __main__ import sieve;sieve(100)") > 7.819571657778932 > > u

Re: [Python] numeri primi

2011/8/3 matteo > un aiutino? * default: number=100* ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python

Re: [Python] numeri primi

Il giorno 03 agosto 2011 10:30, Carlos Catucci ha scritto: > Un paio di considerazioni pero' che mi erano venute in mente empo fa > al riguardo sono che oltre a non essere pari (quindi si pososno > saltare) non sono multipli appunto di 3, 5 e 7. Quindi un meccanismo > (non ho ancora scxritto il c

Re: [Python] numeri primi

> È più o meno quello che fa l'algoritmo proposto da Matteo Dimostrazione che come per Belle e Meucci, idee simili vengono a piu' persone in luoghi e tempi diversi Carlos -- Se i tempi non meritano la tua parte migliore, inventa altri tempi. (Antico detto Baol - S. Benni - Baol)

Re: [Python] numeri primi

Il 03/08/2011 10:54, Daniele Zambelli ha scritto: Il giorno 03 agosto 2011 10:30, Carlos Catucci mailto:carlos.catu...@gmail.com>> ha scritto: Un paio di considerazioni pero' che mi erano venute in mente empo fa al riguardo sono che oltre a non essere pari (quindi si pososno saltare

Re: [Python] numeri primi

Marco, siccome sto sviluppando un codice per risolvere i sistemi lineari a qualsiasi numero di incognite, posso usare il codice di Fabrizio per semplificare i sistemi? P.S.: era per questo che stavo preparando quell'algoritmo sui primi ___ Python mail

Re: [Python] numeri primi

> si, solo che ,al posto di testarli per i numeri minori della metà di quello > in esame , testa per tutti quei primi minori dell'intero della radice (che è > meglio ;) ) Effettivamente e' una operazione molto piu' immediata Carlos -- Se i tempi non meritano la tua parte migliore, inventa altri

Re: [Python] numeri primi

http://it.wikipedia.org/wiki/Crivello_di_Atkin quest'algoritmo dovrebbe essere uno tra i più rapidi, magari può tornarvi comodo :) Il 03 agosto 2011 11:04, Carlos Catucci ha scritto: >> si, solo che ,al posto di testarli per i numeri minori della metà di quello >> in esame , testa per tutti quei

Re: [Python] numeri primi

2011/8/3 Filadelfo Fiamma http://it.wikipedia.org/wiki/Crivello_di_Atkin > > quest'algoritmo dovrebbe essere uno tra i più rapidi, magari può > tornarvi comodo :) > ah, dici? http://www.enrico-franchi.org/2011/07/atkin-for-everyone-benchmark.html ___

Re: [Python] numeri primi

come complessità computazionale credo sì... ma non vorrei dire caxxate :D Il 03 agosto 2011 11:10, Marco Mariani ha scritto: > 2011/8/3 Filadelfo Fiamma > >> http://it.wikipedia.org/wiki/Crivello_di_Atkin >> >> quest'algoritmo dovrebbe essere uno tra i più rapidi, magari può >> tornarvi comodo :

Re: [Python] numeri primi

Il 03/08/2011 11:15, Filadelfo Fiamma ha scritto: come complessità computazionale credo sì... ma non vorrei dire caxxate :D Il 03 agosto 2011 11:10, Marco Mariani ha scritto: 2011/8/3 Filadelfo Fiamma http://it.wikipedia.org/wiki/Crivello_di_Atkin quest'algoritmo dovrebbe essere uno tra i p

Re: [Python] numeri primi

indubbiamente, per eccellenza risulterà più veloce di qualunque altra cosa :). Io intendevo che matematicamente Atkin risulta essere uno tra i più efficienti, poi ovviamente scontrandosi con il mondo della programmazione è plausibile che l'efficienza a livello logico subisca un degrado di pari pass

Re: [Python] numeri primi

2011/8/3 matteo > Marco, siccome sto sviluppando un codice per risolvere i sistemi lineari a > qualsiasi numero di incognite, posso usare il codice di Fabrizio per > semplificare i sistemi? > P.S.: era per questo che stavo preparando quell'algoritmo sui primi Dovresti chiedere a lui (che ho rim

Re: [Python] numeri primi

2011/8/3 Marco Mariani > > http://www.enrico-franchi.org/2011/07/atkin-for-everyone-benchmark.html > Hai provato l'algoritmo di Fabrizio? Tra l'altro la versione senza bitmask era più veloce ma usava più ram. Magari te la può mandare. Ciao. Marco. -- http://beri.it/ - Un blog http://beri.it

Re: [Python] numeri primi

Marco Mariani wrote: ah, dici? http://www.enrico-franchi.org/2011/07/atkin-for-everyone-benchmark.html Hei, quelle sono tutte versioni *ingenue*. Il punto non era ottimizzare il codice. Comunque si, Atkin e' piu' veloce asintoticamente. Il problema e' che e' piu' veloce di un fattore log

Re: [Python] numeri primi

Matteo Presutto wrote: > ma secondo me piu che questione di computazione, qua è questione > di interpretazione, mi spiego meglio, python è un linguaggio > interpretato, e ha bisogno di troppi passaggi prima della > compilazione... a mio parere, se si vuole fare un programma davvero > veloce per tro

Re: [Python] numeri primi

Marco Beri wrote: http://www.enrico-franchi.org/2011/07/atkin-for-everyone-benchmark.html Hai provato l'algoritmo di Fabrizio? Si. E' sconvolgentemente veloce essendo pure python. Comunque questo e' il mio eratostene (sono 5 righe): % time python erat_matrix.py 1 (array([

Re: [Python] numeri primi

> matteo wrote: >> Marco, siccome sto sviluppando un codice per risolvere i sistemi >> lineari a qualsiasi numero di incognite, posso usare il codice >> di Fabrizio per semplificare i sistemi? Marco Beri wrote: > Dovresti chiedere a lui (che ho rimesso in cc). > > Comunque mi ha appena segnalato

Re: [Python] numeri primi

Carlos Catucci wrote: > Dimostrazione che come per Belle e Meucci Non erano Belle e Sebastien? ;-) -- Nicola Larosa - http://www.tekNico.net/ I have come to see cities as ugly, fragile and crumbling human artifacts that deny and work against nature. Likewise farms and fields, monocultural lands

Re: [Python] numeri primi

Enrico Franchi wrote: Sulla mia macchina: % time python -c "import km;km.sieve(1)" python -c "import km;km.sieve(1)" 9.10s user 0.21s system 97% cpu 9.580 total Adesso vedo se riesco ad aggiungerci una qualche micro-ottimizzazione (al mio). % time python erat_matrix.py 100

Re: [Python] numeri primi

2011/8/3 Enrico Franchi > Enrico Franchi wrote: > >> Sulla mia macchina: >> % time python -c "import km;km.sieve(1)" >> python -c "import km;km.sieve(1)" 9.10s user 0.21s system 97% >> cpu 9.580 total >> >> Adesso vedo se riesco ad aggiungerci una qualche micro-ottimizzazione >>

Re: [Python] numeri primi

Gmpy non la usa nessuno? Io ora sono su un netbook quindi e` abbastanza sleale, pero` io alla fine ho usato quella per project eulero! (Grazie Alex :D ) 2011/8/3 Enrico Franchi : > Enrico Franchi wrote: >> >> Sulla mia macchina: >> % time python -c "import km;km.sieve(1)" >> python -c "imp

Re: [Python] numeri primi

Il 03/08/2011 16:52, Marco Beri ha scritto: 2011/8/3 Enrico Franchi > Enrico Franchi wrote: Sulla mia macchina: % time python -c "import km;km.sieve(1)" python -c "import km;km.sieve(1)" 9.10s user 0.21s syste

Re: [Python] numeri primi

Andrea Ambu wrote: Gmpy non la usa nessuno? I IIRC li di veloce c'e' solo miller rabin. -- . ..: -enrico- ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python

Re: [Python] numeri primi

2011/8/3 Matteo Presutto > un pò cos'è la funzione yield e come funziona http://www.enricozini.org/2007/pygnami/generatori/ ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python

Re: [Python] numeri primi

Marco Beri wrote: Ma ce le fai vedere o no queste 5 e poi 15 righe? O sono scienza segreta? :-) def erat_basic(buffer, end): limit = int(math.ceil(math.sqrt(end))) buffer[0] = buffer[1] = 0 for i in xrange(2, limit): if buffer[i]: buffer[np.arange(2*i, end, step

Re: [Python] numeri primi

carissimi pythoniani, esiste un modo per sapere in che punto della memoria si trova il valore di una variabile? per dare un idea: come in c++ per i puntatori, così posso collegare due programmi diversi per svolgere una stessa funzione ;) ___ Python m

Re: [Python] numeri primi

On Wed, 03 Aug 2011 20:07:34 +0200, Matteo Presutto wrote: > carissimi pythoniani, esiste un modo per sapere in che punto della > memoria si trova il valore di una variabile? per dare un idea: come in > c++ per i puntatori, così posso collegare due programmi diversi per > svolgere una stessa fu

Re: [Python] numeri primi

Fermi restanti i sacrosanti[0] avvertimenti di piro, 2011/8/3 Daniele Varrazzo : > Se ci provi il sistema operativo ti taglia le manine :) Il puntatore in > memoria di una variabile ce l'hai con la funzione id(), ma processi diversi > non possono accedere alla stessa area di memoria "normale". Que

Re: [Python] numeri primi

se vuoi far comunicare due processi davvero indipendenti o che devono restare tali, ti consiglio di dare una occhiata a zeromq oppure a dbus. Il giorno 03/ago/2011 22:03, "Carlo Miron" ha scritto: > Fermi restanti i sacrosanti[0] avvertimenti di piro, > > 2011/8/3 Daniele Varrazzo : >> Se ci provi

Re: [Python] numeri primi

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)

Re: [Python] numeri primi

Scusate, ho sbagliato a ricostruire l'indentazione: 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: br