[C] Crivello di eratostene

[Ir0nM4id3n84]

Questo è quanto ci è stato fornito:
Descrizione
I numeri primi si definiscono in matematica come quei numeri naturali che sono divisibili solo per 1 e per se stessi. Esiste un antichissimo metodo (forse uno dei primi algoritmi di cui si abbia conoscenza) per generare tutti i numeri primi da 1 ad N, noto come Crivello di Eratostene, che risale al III secolo avanti Cristo: si scrivono tutti i numeri naturali da uno a N. Si comincia da 2 e si cancellano tutti i suoi multipli (4,6,8,10, ...). Si prende il prossimo numero non cancellato, il 3, e si cancellano tutti i suoi multipli (6,9,12,15, ...). A questo punto il primo numero non cancellato è il 5 e si cancellano i suoi multipli, e cosi' via. Alla fine, seguendo questo procedimento, i numeri non cancellati sono tutti i numeri primi tra 1 e N. (quando ci si può fermare in realtà?).

Voi dovrete semplicemente scrivere un programma che:

genera tutti i numeri primi da 1 a 10000 [SUGG: usare un array, inizializzare tutti i suoi elementi a 1; poi applicare l'algortimo di Eratostene, dove cancellare il numero i, significa porre a 0 l'iesimo elemento dell'array];
accetta in input un'intero positivo e si comporta nel seguente modo:
se l'intero è 0 si ferma;
se l'intero è compreso tra 1 e 10000, stampa 1 se il numero è primo, 0 altrimenti e poi aspetta in input un nuovo numero;
se l'intero è negativo o strettamente maggiore di 10000, stampa -1 e poi chiede in input un nuovo numero.


Io ho pensato di svilupparlo nel seguente modo...per faovre ditemi se è un'idea intelligente o fallimentare.

Nel main dichiaro un array di dimensioni SIZE definite mediante una define.
Invoco una funzione chiamata inizializza che mi inizzializza tutti gli elementi del vettore ad 1

Poi chiamo una funzione che mi elimina tutti i multipli di 2 (vede se il numero%2 !=0 allora lo elimina)
Poi faccio la stessa cosa con una funzione che elimina tutti i multipli di 3
chiamo una funzione che elimina tutti i multipli di 5 e infine chiamo una funzione che elimina tutti i multipli di 7 e così dovrei aver trovato i numeri primi....

Giusto?

[AnonimoVeneziano]

Originariamente inviato da Ir0nM4id3n84
Questo è quanto ci è stato fornito:
Descrizione
I numeri primi si definiscono in matematica come quei numeri naturali che sono divisibili solo per 1 e per se stessi. Esiste un antichissimo metodo (forse uno dei primi algoritmi di cui si abbia conoscenza) per generare tutti i numeri primi da 1 ad N, noto come Crivello di Eratostene, che risale al III secolo avanti Cristo: si scrivono tutti i numeri naturali da uno a N. Si comincia da 2 e si cancellano tutti i suoi multipli (4,6,8,10, ...). Si prende il prossimo numero non cancellato, il 3, e si cancellano tutti i suoi multipli (6,9,12,15, ...). A questo punto il primo numero non cancellato è il 5 e si cancellano i suoi multipli, e cosi' via. Alla fine, seguendo questo procedimento, i numeri non cancellati sono tutti i numeri primi tra 1 e N. (quando ci si può fermare in realtà?).

Voi dovrete semplicemente scrivere un programma che:

genera tutti i numeri primi da 1 a 10000 [SUGG: usare un array, inizializzare tutti i suoi elementi a 1; poi applicare l'algortimo di Eratostene, dove cancellare il numero i, significa porre a 0 l'iesimo elemento dell'array];
accetta in input un'intero positivo e si comporta nel seguente modo:
se l'intero è 0 si ferma;
se l'intero è compreso tra 1 e 10000, stampa 1 se il numero è primo, 0 altrimenti e poi aspetta in input un nuovo numero;
se l'intero è negativo o strettamente maggiore di 10000, stampa -1 e poi chiede in input un nuovo numero.


Io ho pensato di svilupparlo nel seguente modo...per faovre ditemi se è un'idea intelligente o fallimentare.

Nel main dichiaro un array di dimensioni SIZE definite mediante una define.
Invoco una funzione chiamata inizializza che mi inizzializza tutti gli elementi del vettore ad 1

Poi chiamo una funzione che mi elimina tutti i multipli di 2 (vede se il numero%2 !=0 allora lo elimina)
Poi faccio la stessa cosa con una funzione che elimina tutti i multipli di 3
chiamo una funzione che elimina tutti i multipli di 5 e infine chiamo una funzione che elimina tutti i multipli di 7 e così dovrei aver trovato i numeri primi....

Giusto?


Non sembra difficile, e a me piacciono sti giochetti :D

Domani quando ho tempo lo faccio :p

CIao e grazie per il nuovo intrattenimento :D

Comunque a me a prima vista verrebbe + idea di usare degli array dinamici anzichè statici in modo da ridimensionarli dopo la cancellazione dei vari elementi e (soprattutto) in modo da non limitare il numero massimo di elementi da computare alla grandezza dell'array specificato nel codice .

Ciao

[AnonimoVeneziano]

Ehehe , l'ho fatto.

L'ho fatto in 10 minuti prima di andare a dormire , quindi non vi aspettate niente di ordinato o ottimizzato , è abbastanza semplice come programma e per funzionare funziona :p



#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[]) {

int *array1 = NULL, *arrayh = NULL, size = 0, count = 0, bigcount = 1, count2 = 0;
if (argc == 2) {
size = atoi(argv[1]);

array1 = calloc(size, sizeof(int));

for(; count < size; count++)
array1[count] = count+1;

while (bigcount < size) {

for ( count = bigcount+1; count < size; count++ ) {

if ( (array1[count] % array1[bigcount]) == 0 )
array1[count] = 0;
}

for (count = 0; count < size; count++) {

if ( array1[count] != 0 )
count2++;

}

arrayh = calloc(count2, sizeof(int));

count2 = 0;

for ( count = 0; count < size; count++)
if ( array1[count] != 0 ) {
arrayh[count2] = array1[count];
count2++;
}
free(array1);

array1 = arrayh;

bigcount++;

size = count2;
count2 = 0;
}

for ( count = 0; count < size; count++ )

printf("%d\n", array1[count]);
}
else
printf("[USAGE]primi [n°di numeri primi da trovare]\nEsempio:\n\nprimi 30\n\nTrova tutti i numeri primi da 1 a 30\n");

return 0;

}



Ciao

PS = per usarlo da linea di comando si scrive il nome del programma e poi l'intervallo di numeri nel quale trovare i numeri primi (Ad es ponendo che l'eseguibile si chiami "primi" : "primi 30" trova tutti i primi da 1 a 30 col metodo di eratostene)

[VICIUS]

Belli questi programmini. :D
questa è la mia versione.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int main (int argc, char** argv)
{
if (argc != 2) return -1;

int lim = atoi (argv[1]);
if (lim < 2) return -2;

int* list = calloc (sizeof (int), lim);
for (int i = 2; i <= lim; i++)
list[i] = i;

float max = sqrt (lim);
for (int i = 2; i < max; i++)
{
if (list[i] == 0) continue;

for (int j = i + 1; j < lim; j++)
if (list[j] % i == 0)
list[j] = 0;
}

for (int i = 2; i < lim; i++)
if (list[i] != 0) printf ("%d ", list[i]);

free (list);
return 0;
}


ciao ;)

[AnonimoVeneziano]

Originariamente inviato da VICIUS
Belli questi programmini. :D
questa è la mia versione.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int main (int argc, char** argv)
{
if (argc != 2) return -1;

int lim = atoi (argv[1]);
if (lim < 2) return -2;

int* list = calloc (sizeof (int), lim);
for (int i = 2; i <= lim; i++)
list[i] = i;

float max = sqrt (lim);
for (int i = 2; i < max; i++)
{
if (list[i] == 0) continue;

for (int j = i + 1; j < lim; j++)
if (list[j] % i == 0)
list[j] = 0;
}

for (int i = 2; i < lim; i++)
if (list[i] != 0) printf ("%d ", list[i]);

free (list);
return 0;
}


Effettivamente ci ho messo un po' di allocazioni di memoria inutili , ma vi prego, contate anche la stanchezza

:sofico:


Scusa una cosa vic , ma questo l'hai messo solo per aumentare la velocità del codice , vero?

float max = sqrt (lim);

Difatti ho notato che togliendolo il tutto diventa molto + lento , ma su che basi ipotizzi che il numero massimo di iterazioni del ciclo FOR che fai sotto sarà la radice quadrata del numero limite? Mi interesserebbe capire

Ciao

[VICIUS]

Originariamente inviato da AnonimoVeneziano
Effettivamente ci ho messo un po' di allocazioni di memoria inutili , ma vi prego, contate anche la stanchezza

:sofico:


Scusa una cosa vic , ma questo l'hai messo solo per aumentare la velocità del codice , vero?

float max = sqrt (lim);

Difatti ho notato che togliendolo il tutto diventa molto + lento , ma su che basi ipotizzi che il numero massimo di iterazioni del ciclo FOR che fai sotto sarà la radice quadrata del numero limite? Mi interesserebbe capire

Ciao
Se p è il piu piccolo divisore primo del numero a abbiamo che a = p * r con r che deve essere >= di p. Quindi a = p * r che è >= p * p che è = p². Quindi ne consegue che p è semre minore o uguale alla radice quadrata di a.

ciao ;)

[AnonimoVeneziano]

Originariamente inviato da VICIUS
Se p è il piu piccolo divisore primo del numero a abbiamo che a = p * r con r che deve essere >= di p. Quindi a = p * r che è >= p * p che è = p². Quindi ne consegue che p è semre minore o uguale alla radice quadrata di a.

ciao ;)

Azzo , non la sapevo sta regola qua, è arguta .

Ho provato anche a fare una versione senza tutte quelle allocazioni di memoria , ma mi è risultata addirittura + lenta di quella con le allocazioni di memoria mah , boh .


Ciao

[repne scasb]

[AnonimoVeneziano]

time ./primi 100000 (IO)

real 0m3.646s
user 0m2.084s
sys 0m0.013s

time ./vicprim 100000 (VICIUS)

real 0m0.956s
user 0m0.184s
sys 0m0.006s

time ./repne 100000 (REPNE)

real 0m0.357s
user 0m0.007s
sys 0m0.003s

Direi che la vincitrice di tappa è Repne per ora :D

[repne scasb]

[a2000.1]

Originariamente inviato da AnonimoVeneziano
time ./primi 100000 (IO)

real 0m3.646s
user 0m2.084s
sys 0m0.013s

time ./vicprim 100000 (VICIUS)

real 0m0.956s
user 0m0.184s
sys 0m0.006s

time ./repne 100000 (REPNE)

real 0m0.357s
user 0m0.007s
sys 0m0.003s

Direi che la vincitrice di tappa è Repne per ora :D

7 istruzioni
PIII 350MHz
VBA
1000000 (un milione)

tempo di calcolo = 0.24 s

:rotfl:

[VICIUS]

Originariamente inviato da a2000.1
7 istruzioni
PIII 350MHz
VBA
1000000 (un milione)

tempo di calcolo = 0.24 s

:rotfl:
è no ora ci devi fare vedere il codice altrimenti non ci credo :p

ciao ;)

[a2000.1]

pronti :)


Const iMax = 10000000, kMax = Int((iMax + 1) / 2)
Dim aaa(1 To kMax) As Integer 'bit

For k = 2 To Int((Sqr(iMax) - 1) / 2)
If aaa(k) = 0 Then
For h = 3 * k - 1 To kMax Step 2 * k - 1
aaa(h) = 1
Next h
End If
Next k

[repne scasb]

[VICIUS]

Originariamente inviato da a2000.1
pronti :)


Const iMax = 10000000, kMax = Int((iMax + 1) / 2)
Dim aaa(1 To kMax) As Integer 'bit

For k = 2 To Int((Sqr(iMax) - 1) / 2)
If aaa(k) = 0 Then
For h = 3 * k - 1 To kMax Step 2 * k - 1
aaa(h) = 1
Next h
End If
Next k


thx. pero questo non è proprio il crivello di erotestene giusto ? almeno non ci assomiglia (di vba conosco solo il nome quindi potrei sbagliarmi).

in ogni caso le nostre versioni perdono la maggior parte del tempo a fare output con printf e ad aspettare il terminale. togliendo gli output diventa tutto molto piu veloce.

ciao ;)

[AnonimoVeneziano]

Originariamente inviato da VICIUS
thx. pero questo non è proprio il crivello di erotestene giusto ? almeno non ci assomiglia (di vba conosco solo il nome quindi potrei sbagliarmi).

in ogni caso le nostre versioni perdono la maggior parte del tempo a fare output con printf e ad aspettare il terminale. togliendo gli output diventa tutto molto piu veloce.

ciao ;)


Sei un coniglio :D

[VICIUS]

Originariamente inviato da AnonimoVeneziano
Sei un coniglio :D
Zitto tu. :D

[cionci]

Guadate questo:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main(int argc, char *argv[])
{
int max, size, i, j, z;
char *list;

if(argc < 2)
return 1;
if((max = atoi(argv[1])) <= 2)
return 1;
size = (max / 2 + 1);
if((list = (char *)calloc(sizeof(char), size)) == NULL)
return 1;
for(i=0; i<size; i++)
list[i]=0;

printf("%6d ", 2);

for(j=1,i=3; i<max; ++j,i+=2)
{
if(list[j] == 0)
{
for(z=j+i; z<size; z+=i)
list[z] = -1;
printf("%6d ", i);
}
}

return 0;
}

Questo mi risulta essere un pelino più veloce di quello di repne scasb...

[cionci]

Comuqnue sarebbe meglio contare il tutto senza output...altrimenti le differenze sono poco apprezzabili...

[repne scasb]

[repne scasb]

[repne scasb]

[cionci]

Originariamente inviato da repne scasb
No, e' il 32% piu' lento. Riprova sarai piu' fortunato.

Prova con 100.000.000 altrimenti devi avere un timer molto preciso per valutare i tempi.

Su Athlon 1466 io 22 secondi tu 32 secondi (100.000.000) la printf viene eseguita, ma con output disattivo.
A me su un Athlon @ 2100 Mhz risulta che il mio impiega 7 secondi e il tuo 23...senza output...e per 100.000.000... Sarà una questione di compilatore...Visual C++ in questo caso...ora provo con MinGW32...

[cionci]

Probabilmente avevo copiato una versioen sbagliata del tuo codice...
Comunque ora il mio ci mette 4 secondi per 100000000 numeri...
Mentre il tuo 9 secondi....sempre con printf commentate...


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main(int argc, char *argv[])
{
int max, lim, size, i, j, z;
char *list;

if(argc < 2)
return 1;
if((max = atoi(argv[1])) <= 2)
return 1;

size = (max / 2 + 1);
if((list = (char *)calloc(sizeof(char), size)) == NULL)
return 1;
for(i=0; i<size; i++)
list[i]=0;

printf("2 ");

lim = (int)sqrt(max);

for(j=1,i=3; i<=lim; ++j,i+=2)
{
if(!list[j])
{
for(z=j+i; z<size; z+=i)
list[z] = -1;
printf("%d ", i);
}
}

for(; i<max; i+=2, ++j)
if(!list[j])
printf("%d ", i);

return 0;
}

[cionci]

Ho riguardato ed ho visto che la differenza principale era nella struttura del vettore (io l'ho fatto di char)...che rende il programma più veloce del 45%... Mettendo comunque int (come nel tuo) faccio due secondi meno del tuo ;)

[repne scasb]

[cionci]

Possibile...ma quel 30% in più sono solo INC...mentre le tuo sono più pesanti perchè sono moltiplicazioni ;)

[repne scasb]

[cionci]

Originariamente inviato da repne scasb
Se guardi con un profiler il tuo software e il mio ti renderai conto che il tuo software fa il 37.43% in piu' di operazioni complessive. Purtroppo qui il problema e' la RAM. A parita' di "consumo di RAM, nonostante il mi software faccia oltre il 30% in meno di operazioni, i risultati sono (a parita' di compilatore e di ottimizzazioni):

IO: 100.000.000 -> Athlon 1466 -> 289 ticks
TU: 100.000.000 -> Athlon 1466 -> 326 ticks
Hai preso la nuova versione del mio...vero ? Mi ero scordato di implementare la limitazione della radice quadrata...

[a2000.1]

20 istruzioni
PIV 2GHz
Fortran95
100000000 (cento milioni)

tempo di calcolo = 0.63 s

:rotfl:

[repne scasb]

[cionci]

Ecco qua con gli int...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main(int argc, char *argv[])
{
int max, lim, size, i, j, z;
int *list;

if(argc < 2)
return 1;
if((max = atoi(argv[1])) <= 2)
return 1;

size = (max / 2 + 1);
if((list = (int *)calloc(sizeof(int), size)) == NULL)
return 1;
for(i=0; i<size; i++)
list[i]=0;

printf("2 ");

lim = (int)sqrt(max);

for(j=1,i=3; i<=lim; ++j,i+=2)
{
if(!list[j])
{
for(z=j+i; z<size; z+=i)
list[z] = -1;
printf("%d ", i);
}
}

for(; i<max; i+=2, ++j)
if(!list[j])
printf("%d ", i);



Nota che non facio nemmeno una moltiplicazione ;)

[cionci]

Originariamente inviato da a2000.1
20 istruzioni
PIV 2GHz
Fortran95
100000000 (cento milioni)

tempo di calcolo = 0.63 s

:rotfl:
Cidice...codice...

[a2000.1]

prefettato sfizzero ®®®®®®®®®®® :rotfl: :sborone:

[cionci]

Originariamente inviato da a2000.1
prefettato sfizzero ®®®®®®®®®®® :rotfl: :sborone:
Allora non vale...non puoi brevettare il crivello di Eratostene...

[repne scasb]

[a2000.1]

Originariamente inviato da cionci
Allora non vale...non puoi brevettare il crivello di Eratostene...

il crivello di Eratostene no, ma quello di E...o.t...E.a...t.n...a.o...n. sì !!! :)

[repne scasb]

[a2000.1]

Originariamente inviato da repne scasb
Allora, "E' il QUAD PUMPED DEL PENTIUM IV SU RAM DDR CHE PAGA".
...



no è un paio d'anni sul quarter-pumped dell'assembler dell'hp45 che pagano... a distanza ... ma pagano, anche se in CHF. :D

[cionci]

Originariamente inviato da a2000.1
no è un paio d'anni sul quarter-pumped dell'assembler dell'hp45 che pagano... a distanza ... ma pagano, anche se in CHF. :D
Non mi dire che sei un esperto programmatore di HP45 :) Mitico...

[a2000.1]

sistema lineare NxN con input dati da display tipo A(43, 67) = ? in 97 istruzioni. :)

[cionci]

La HP45 è per i vecchietti come te...ai miei tempi c'era la HP48 ;)

[a2000.1]

invece oggi il collega mostrommi un Crivello di John Holmes, fedele calco in lattice nero, ancora imballato, che portava in dono alla sua insaziabile amante del prandiale :O

[a2000.1]

Originariamente inviato da cionci
La HP45 è per i vecchietti come te...ai miei tempi c'era la HP48 ;)

anche quel catafalco dell'HP48 ... :O
ma solo fino a quando l'ha messa a cuocere mio figlio nel camino :D

[a2000.1]

a proposito di vecchietti ... ma ti sei laureato o no ? :)

[cionci]

Originariamente inviato da a2000.1
a proposito di vecchietti ... ma ti sei laureato o no ? :)
:fiufiu: :fiufiu: :fiufiu: :fiufiu: :fiufiu: :ops:

[a2000.1]

dai dai che dopo ti porto nel forziere di Zio Paperone !!! :D

[repne scasb]

[Darker]

Sono decisamento niubbo, ma c'ho provato anche io :D

#include <stdio.h>

main(){
int i[100];
int j,m,k = 2;
for (j=0;j<100;j++)
i[j]=j;
loop:
m=k;
while (k<100){
k=k+m;
i[k]=0;
}


ciclo:

k=m+1;
if (k<100){
if (i[k]!=0)
goto loop;

else{
m=k;
goto ciclo;
}
}
else {
for (j=0;j<100;j++){
if (i[j]!=0)
printf("%d\n", i[j]);
}
}

}



Inutile dire che se metto 10000000 al posto di 100, mi sputa un infido segmentation fault perchè l'array è troppo grande... ma vabbè... ci lavorerò :D

Non deridetemi troppo ^^;

[repne scasb]

[cionci]

Puoi misurare il tempo di esecuzione ?
A me il tuo nuovo non mi funziona a dovere...non so perchè...

PS: al loop prima di due e poi di 4 c'ero arrivato anche io... Lo stavo per implementare ;)

[repne scasb]

[cionci]

Ok...allora misura il tempo di esecuzione sul tuo computer ;)

Quindi il mio algoritmo se pur meno efficiente del tuo reisce ancora a batterti su un PC come meno di 1 Gb di ram :asd: :fuck::flower:

Ora comunque implemento anche il salto di prima di 2 e poi di 4...

[repne scasb]

[repne scasb]

[cionci]

Ho convertito entrambi i vettori a char...ma a me il tuo va comunque pianissimo... Non capisco il perchè... Prova a misurare acnhe te il tempo di entrambi...

Ripensandoci fare il salto 2,2,2,4 almeno per me è solamente uno spreco di tempo... Le operazioni saltate saranno solamente due somme e due confronti...ovvero un ciclo ogni 5 cicli esterni... Ma non sono questi cicli esterni che pesano sul risultato finale (visto che in quel ciclo esterno saltato non sarei comunque entrato nel ciclo interno perchè l'elemento è marcato come multiplo di 5)...

[cionci]

Anzi...ora che ci penso...perchè fai il loop una volta di 2 ed un volta di 4 ?!?!??

Non mi torna...

Ad esempio eni primi 20 numeri quelli da testare come primi (dopo 5) sono :

7 9 11 13 15 17 19...l'unico ciclo che si può saltare a priori è quello del 15... Quindi l'avanzamento dovrebbe essere 2, 2, 2, 4, 2 e non una volta 2 ed una volta 4....

[repne scasb]

[repne scasb]

[cionci]

Probabilemnte ai regione eprchè io facevo il conto su ogni decade...aspetta che mi riguardo...

[cionci]

Ah ho capiito...salti atuomaticamente anche i multipli di 3...

[repne scasb]

[repne scasb]

[cionci]

Ah...ecco...questo è il primo che alla prova dei fatti va più veloce del mio... Gi altri a me andavano tutti più lenti...

3225 ms contro 5149 ms del mio (usando i char)...

[cionci]

Originariamente inviato da repne scasb
Adesso salto anche 5 "completamente", se vuoi spingo ancora.
Nono...non importa...la tecnica è quella...

[repne scasb]

[cionci]

Originariamente inviato da repne scasb
E' un problema di frammentazione della RAM
Avevo messo anche nel mio gli int... Magari ero avvantaggiato perchè usavo la metà della Ram che usavi tu...

[repne scasb]

[Ir0nM4id3n84]

ahaha ma ho scatenato il tormentone del forum...io lo devo ancora fare...dohh...domani ho la consgna....tocca studia :D

[repne scasb]

[RaouL_BennetH]

per repne scasb, cionci, vicius, ilsensine e gli altri guru

Una semplice richiesta:

Se non vi scoccia, all'interno del codice che postate, potreste inserire anche qualche commento, in modo da poter permettere anche a chi, come me, niubbo ed inesperto, se non di comprendere totalmente, almeno potremo "tentare" di farci un'idea su come opera.

Thx.

RaouL.

[cionci]

Originariamente inviato da RaouL_BennetH
per repne scasb, cionci, vicius, ilsensine e gli altri guru

Una semplice richiesta:
Presto fatto:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char *argv[])
{
int max, lim, size, i, j, z;
char *list;

if(argc < 2)
return 1;

/* prendo dalla linea di comando il numero massimo e lo converto in intero */
if((max = atoi(argv[1])) <= 2)
return 1;

/* mi segno solamente gli elementi dispari */
size = max / 2 + 1;
/* alloco il vettore che dovrà contenere i marker deglie elementi dispari*/
if((list = (char *)calloc(sizeof(char), size)) == NULL)
return 1;

/* azzero il vettore, se un elemento è 0 allora è primo, se -1 non è primo*/
for(i=0; i<size; i++)
list[i]=0;

printf("%d ", 2);

/* il limite di ricerca sarà pari alla radice quadrata
del massimo (come visto prima nel thread) */
lim = (int)sqrt(max);

/* scorro il vettore con j (un elemento alla volta),
scorro gli interi dispari tra 3 e lim */
for(j=1,i=3; i<=lim; ++j,i+=2)
/* se list[j] è primo: l'elemento j fa riferimento all'intero 2*j+1 */
if(!list[j])
{
/* scorro tutto il vettore spostandomi da j+i (che fa riferimento
all'intero 2*(j+i)+1) con passo i (corrispondente a 2*i interi).
In questo modo non tengo conto degli interi pari */
for(z=j+i; z<size; z+=i)
/* segno come non primo perchè multiplo di i */
list[z] = -1;
printf("%d ", i);
}

/* una volta raggiunto lim, il resto degli elementi segnati con 0 è primo */
for(; i<max; i+=2, ++j)
if(!list[j])
printf("%d ", i);

return 0;
}

[repne scasb]

[cionci]

Se posso aiutatrti nella spiegazione: segnativi su un foglio gli interi fra 5 e 20...

Fate una crocetta sui multipli di 2 e di 3... Contate (ed aggiungeteci uno), partendo dal primo numero senza crocetta, la quantità di numeri con crocetta da saltare per raggiungere il numero non eliminato successivo...

Questa sequenza rispetta un dato schema... Nel caso abbiate eleminato solo i multipli di due e di tre è {2, 4} e poi si ripete...

Eliminate anche i multipli di 5 e partite a contare da 7... Lo schema questa volta sarà {4,2,4,2,4,6,2,6} e poi si ripeterà...

Se elimnate anche i multipli di 7 e partite a contare da 11 lo schema sarà quello postato da repne scasb nell'utimo codice...

In pratica sapendo a priori questo schema, restringiamo il campo di ricerca saltando, secondo lo schema, da un numero ad un altro...

[Angus]

Originariamente inviato da cionci
Presto fatto:

...
/* scorro il vettore con j (un elemento alla volta),
scorro gli interi dispari tra 3 e lim */
for(j=1,i=3; i<=lim; ++j,i += i - 1)
...


probabilmente così si possono saltare un pò di cicli esterni, ma non ho verificato matematicamente la mia conclusione... se qualcuno ha voglia di provare a confutare o dimostrare...

posto il codice java che mi tira fuori i numeri che a me 'sembrano' primi:


import java.util.Arrays;


public class Eratostene {
public static void main(String[] args) {
if (args.length != 1) {
System.exit(1);
}
int n = Integer.parseInt(args[0]);
long start = System.currentTimeMillis();

// non c'è ottimizzazione sui pari e cose simili, per semplicità

// alloco l'array
int[] primi = new int[n];
// riempio l'array con 1
Arrays.fill(primi, 1);
// ciclo esterno: f è il fattore preso in condiderazione
for (int f = 2; f * f < n; f += f - 1) {
// se il fattore non è stato eliminato entra nel ciclo interno
if (primi[f] == 1) {
// ciclo interno: elimino tutti i multipli m del fattore
for (int m = 2 * f; m < n; m += f) {
primi[m] = 0;
}
}
}
long stop = System.currentTimeMillis();
// for (int i = 1; i < n; i++) {
// if (primi[i] != 0) System.out.println(i);
// }
System.out.println("Time elapsed: " + (stop - start));
}
}

[repne scasb]

[cionci]

Ne restano molti in più di primi che non sono primi ;)

[Angus]

Originariamente inviato da repne scasb
Premesso che non so nulla di "java", se ho ben capito:

La prima volta testi 2 (f=2)
La seconda f+=f-1 ossia 3
La terza f=5
la quarta f=9
la quinta f=17
eccetera eccetera...

Non testi 7, 11, 13....

Potrei pero' aver male interpretato il linguaggio a causa di una sua specifica peluliarita'

mi hai preceduto... spulciando avevo trovato dei numeri non primi :rolleyes:
e comunque no: java non ha la peculiarità di rimediare agli errori stupidi :sofico:

[AnonimoVeneziano]

Ho fatto ank'io una versione più veloce , ma non la posto, tanto le prendo sempre di un secondo da repne e cionci :D (Però ho battuto vic :sofico: )

Ciao

[Angus]

Originariamente inviato da cionci
Ne restano molti in più di primi che non sono primi ;)

Provo a fare un altro errore stupido:


// ciclo esterno: f è il fattore preso in condiderazione
for (int f = 2; f * f < n; f++) {
// se il fattore non è stato eliminato entra nel ciclo interno
if (primi[f] == 1) {
// ciclo interno: elimino tutti i multipli m del fattore f
// a partire da f^2, perchè tutti i precedenti sono stati già
// eliminati
for (int m = f * f; m < n; m += f) {
primi[m] = 0;
}
}
}

[repne scasb]

[a2000.1]

Originariamente inviato da a2000.1
20 istruzioni
PIV 2GHz
Fortran95
100000000 (cento milioni)

tempo di calcolo = 0.63 s

:rotfl:

e quindi nessuno ha fatto meglio del mio codice di un anno fa ???? :( :D :D

e chi riesce a fare 10000000000 (10 miliardi) in 2.4 secondi con macchina standard ??? :D :sborone:

P.S.
e se facessimo un torneo con un 516 euri a testa ???? :eek: :cool:

[Angus]

correggo l'errore, che era già presente prima dell'ottimizzazione (quindi giusta?) di m >= f^2:


// alloco l'array
int[] primi = new int[n + 1];
// riempio l'array con 1
Arrays.fill(primi, 1);
// ciclo esterno: f è il fattore preso in condiderazione
int countf = 0, countm = 0;
for (int f = 2; f * f <= n; f++, countf++) {
// se il fattore non è stato eliminato entra nel ciclo interno
if (primi[f] == 1) {
// ciclo interno: elimino tutti i multipli m del fattore f
// a partire da f^2, perchè tutti i precedenti sono stati già
// eliminati
for (int m = f * f; m <= n; m += f, countm++) {
primi[m] = 0;
}
}
}
long stop = System.currentTimeMillis();
for (int i = 1; i <= n; i++) {
if (primi[i] != 0) System.out.println(i);
}
System.out.println("Time elapsed: " + (stop - start));
System.out.println("Cicli esterni: " + countf);
System.out.println("Cicli interni: " + countm);


la peculiarità non è nel linguaggio java, ma nel modo di allocare l'array, che semplifica un pochino la gestione degli indici, e nella stampa dei numeri primi..

[repne scasb]

[repne scasb]

[a2000.1]

Originariamente inviato da repne scasb
Il risultato "finale" per essere valido deve trovarsi "memorizzato" in un vettore allocato in memoria (crivello di eratostene), e "NON" deve essere valutabile "al volo". Solo per azzerarlo necessitano (REP STOSD) non meno di 1.18 secondi (1 bit per numero), sul mio sistema (non sono validi vettori compressi ad accesso mediante offset).



E' complesso, in quanto, trattandosi di denaro, dovremmo nominare un "curatore" dotato di PC "standard", sul quale vengono eseguiti e valutati i risultati. Ora constatato che io mi fido solo di me stessa, mi dovrei astenere da tale torneo.

In piu' sussiste il problema del linguaggio di programmazione su cui sviluppare l'applicativo. Mi sembra di capire che su tale questione non ci sia un comune accordo, da cui se ne evincerebbe che ogni partecipante al torneo sarebbe autorizzato ad utilizzare il linguaggio di programmazione che piu' gli aggrada.

Considerato che io programmo solo in C, in fortran ma con un "vecchio" compilatore, e in Assembly_x86, mi vedrei costretta a sviluppare l'applicativo in Assembly_x86 in quanto di gran lunga piu' esperta.



macchine e compilatori sono irrilevanti per algoritmi che riducono di 10, 20, 100 volte i tempi di calcolo relativi.
miglioramenti valutabili in xx% non ci interessano.
in tutto.

[cionci]

Comunque noi stavamo sviluppando il crivello di Eratostene e non un algoritmo qualunque...

[Banus]

Originariamente inviato da repne scasb
Se riesci a comprendere come funziona, ti "autorizzo" portare questa versione:
:eek:

Difficile pensare una versione più efficiente. Si potrebbe utilizzare una tabella ancora più lunga che consideri anche 11,13 etc... ma la dimensione cresce rapidamente. La tabella può essere generata facilmente prendendo i primi k numeri primi e applicando il crivello al loro m.c.m. limitandosi a cercare i loro multipli. Nel caso di 11 si deve cercare fra 2*3*5*7*11 numeri.
Con 2,3,5,7 si devono processare l'85% dei numeri che si processavano con 2,3,5. Con 2,3,5,7,11 probabilmente non si guadagna più di un ulteriore 10% e così via aumentando la tabella.

[Angus]

Originariamente inviato da a2000.1
macchine e compilatori sono irrilevanti per algoritmi che riducono di 10, 20, 100 volte i tempi di calcolo relativi.
miglioramenti valutabili in xx% non ci interessano.
in tutto.

concordi appieno con le teorie sulla complessità, e fin qui mi vedi con te. Però qui si cercava di fare altro: tirare fuori tutto quello che si può dallo stesso algoritmo di partenza, senza stravolgere l'algoritmo stesso! Se la sfida non è più sul crivello di Eratostene allora credo che ce ne vorrebbe davvero tanto di tempo da perdere... e sarebbe molto divertente perderlo ;)

[repne scasb]

[Angus]

x repne scasb et al.

spulciando le API di Java, mi salta fuori questo metodo della classe BigInteger:


public static BigInteger probablePrime(int bitLength,
Random rnd)

Returns a positive BigInteger that is probably prime, with the specified bitLength. The probability that a BigInteger returned by this method is composite does not exceed 2^-100



non ho la più pallida idea su cosa si basi per affermare con una certa incertezza che il numero ritornato sia primo...

[Banus]

Originariamente inviato da Angus
non ho la più pallida idea su cosa si basi per affermare con una certa incertezza che il numero ritornato sia primo...
Questa te la posto perchè l'ho pronta :D

http://en.wikipedia.org/wiki/Fermat_primality_test

[cionci]

Originariamente inviato da Banus
Questa te la posto perchè l'ho pronta :D

http://en.wikipedia.org/wiki/Fermat_primality_test
Mi hai anticipato...

[repne scasb]

[Angus]

Originariamente inviato da Banus
Questa te la posto perchè l'ho pronta :D

http://en.wikipedia.org/wiki/Fermat_primality_test

molte grazie :mano: (anche a cionci per l'intenzione)

[cionci]

Originariamente inviato da repne scasb
1) Si cercano n numeri primi con il crivello.
2) Si utilizzano tali numeri per generare la tabella t(..)
3) Si generano m(..) numeri primi successivi a n con la tabella t(..).
4) Si riparte dal punto 2)

Interessante...comunque diventerebbe complesso calcolare la tabella a runtime...

[repne scasb]

[Banus]

Originariamente inviato da cionci
Interessante...comunque diventerebbe complesso calcolare la tabella a runtime...
Infatti è difficile calcolare a priori il numero di elementi della tabella.

[repne scasb]

[cionci]

Originariamente inviato da repne scasb
E' un'idea, nulla piu'. Non ho tempo di svilupparla, ma se ti piacciono le "sfide" mi sembri la persona adatta per cimentarvisi.

Nota: Magari si puo' "riciclare" qualcosa ad ogni iterazione della ricorsione.
Sicurametne si può riciclare qualcosa... Non ne ho tanta voglia ;)

[a2000.1]

confermo:

crivello di Eratostene (implementazione JonhHolmes®)
PC standard (no more than 1200 €)
determinazione dei numeri primi tra 1 e 10^10
tempo di calcolo 2.4 s

quota di partecipazione 516 €.

[Angus]

Originariamente inviato da a2000.1
confermo:

crivello di Eratostene (implementazione JonhHolmes®)
PC standard (no more than 1200 €)
determinazione dei numeri primi tra 1 e 10^10
tempo di calcolo 2.4 s

quota di partecipazione 516 €.

guarda... 516 non li ho, e anche se li avessi oggi proprio non ho tempo... comunque ci penserò su
:sofico:

[cionci]

Originariamente inviato da a2000.1
confermo:

crivello di Eratostene (implementazione JonhHolmes®)
PC standard (no more than 1200 €)
determinazione dei numeri primi tra 1 e 10^10
tempo di calcolo 2.4 s

quota di partecipazione 516 €.
Ma salvi anche i numeri in un vettore ? Cioè il tuo programma torna un vettore con i numeri che sono primi e non primi ?

[repne scasb]

[repne scasb]

[/\/\@®¢Ø]

Originariamente inviato da repne scasb
Non trova la variante al crivello di Eratostene che hai indicato (forse hai commesso un errore di battitura). Ho trovato due matematici che si sono occupati del crivello di Eratostene: William Holmes e John Dyer-Bennet, ma non ho trovato nessuna loro variante comune al crivello di Eratostene.

Ho idea che il John Holmes a cui riferisce a2000.x sia una persona avvezza a ben altri "crivelli" :D
Giusto per restare in tema di facezie, contribuisco con una variante Haskell del crivello, oserei dire pure il crivello nella sua forma piu' pura :D


primes = removeMults (2:[3,5..])
removeMults (n:ns) = n : removeMults ( ns `without` [n,2*n..] )

without (x:xs) (n:ns)
= case compare x n of
LT -> x : xs `without` (n:ns)
EQ -> xs `without` (n:ns)
GT -> (x:xs) `without` ns

[a2000.1]

Originariamente inviato da repne scasb
Non trova la variante al crivello di Eratostene che hai indicato (forse hai commesso un errore di battitura). Ho trovato due matematici che si sono occupati del crivello di Eratostene: William Holmes e John Dyer-Bennet, ma non ho trovato nessuna loro variante comune al crivello di Eratostene.

Sei in grado di fornirmi la documentazione circa tale variante?

Grazie.

:rotfl:

[cionci]

:D John Holmes era un "attore" del "cinema" porno degli anni '80...morto di AIDS... Non è che mi interessi di cinema porno, ma John Holmes è quasi un mito... Hollywood gli ha dedicato persino un film...

Altrimenti c'è l'omaggio dei nostri Elio e Le Storie Tese:

Quand'ero piccolo tutti mi scherzavano
per le dimensioni del mio pene,
ed io non stavo bene.
Soffrivo le pene per colpa del pene,
ma piu' il problema non si pone:
si' perche' il pene mi da' il pane,
son diventato un grande attore
e benche' schiavo dell'amore,
mi son comprato una moto.
E ora son schiavo della moto,
non faccio piu' moto,
infatti vado solo in moto
ma ora son diventato un mito:
ho rilanciato il film muto
perche' sono muto,
e se vedrete il filmato
sicuramente converrete con noi
che questa e' verita'.

John Holmes, una vita per il cinema,
John Holmes, una vita per la moto.
John Holmes, una vita per il cinema,
John Holmes, una vita per la moto.

Trenta centimetri
di dimensione artistica.
Su di cio' la critica e' concorde
nel ritenermi sudicio.
Perche' non hanno capito,
non parlo perche' son rapito,
e poi in faccia non son mai inquadrato
pero' dal pubblico son venerato,
e ora sono diventato un mito:
ho rilanciato il film muto
perche' sono muto,
e se fossi stato ceco
avrei lanciato il film ceco,
e se fossi stato m
avrei lanciato il film m.
Dicon che faccio film penosi
perche' lavoro col pene.
E insomma il pene mi da' il pane,
il pene mi da' si' la moto,
ma la moto non da' pene
perche' funziona bene.
Si' si' la moto non da' pene
perche' funziona bene.

John Holmes, una vita per il cinema,
John Holmes, una vita per la moto.
John Holmes, una vita per il cinema,
John Holmes, una vita per la moto

[a2000.1]

schiusa repne, sei brava ... ma un po' di "divergenza del pensiero" ti farebbe bene.

se vuoi ne parliamo a cena.
per me va bene questo venerdì sera in un posto a piacere tra Zurigo e Roma. :)

[repne scasb]

[repne scasb]

[Angus]

Originariamente inviato da a2000.1
sei brava ... ma un po' di "divergenza del pensiero" ti farebbe bene

anche questa la metto tra le citazioni in sign...

x /\/\@®¢Ø et al:
leggendo questi thread non si finisce mai d'imparare... grazie per avermi fatto conoscere un linguaggio di programmazione (funzionale) molto interessante!

[repne scasb]

[a2000.1]

Originariamente inviato da repne scasb
:rotfl:

non ti devi perplimere:

da divergenza nasce divergenza ...

[a2000.1]

Originariamente inviato da repne scasb
Dopo molto tempo, sono tornata ad andare a pesca. La giornata, non sembrava delle migliori, ma ero dotata di ottima pastura. Ho preso un bel a2000.1 e un curioso cionci; li faro' stasera per cena in padella (sulla tratta Roma-Zurigo)

diciamo che dato il nostro crivello, non abbiamo pregiudizi ...

[cionci]

Ho trovato questo sito molto interessanet: http://www.ieeta.pt/~tos/software/prime_sieve.html

[repne scasb]

[a2000.1]

stai tranquilla che in determinati contesti B.C. con cospicui "quanti" il "chi" è assolutamente secondario :D

[cionci]

Ma il tuo algoritmo ce lo dice "chi" ? Altrimenti non vale ;)

[a2000.1]

e sì, fa la mascheratura finale bit per bit del vettore "contratto".

con C_e_bit potrebbe essere anche meglio. :)

[Angus]

Originariamente inviato da a2000.1
contesti B.C.


:confused:

[repne scasb]

[repne scasb]

[a2000.1]

Originariamente inviato da repne scasb
E' un modo elegante per dire "no".

no è un modo effettive per dire "te lo/a spiego venerdì sera".

[repne scasb]

[a2000.1]

non sai che ti perdi.

[a2000.1]

0.24 secondi di estasi. :D

[cionci]

Come cacchio faccio a fare l'istruzione assmbly RCL in C ? :wtf:
Ovviamente con un solo operatore...

Se non esiste un tale oepratore mi sa che metto un assembly inline...

[repne scasb]

[repne scasb]

[a2000.1]

ingorda ! :oink:

[repne scasb]

[a2000.1]

eh karina ... stai attenta allo spirito dei tempi ... ti potresti ritrovare un alla meno uno quando e dove meno (?) te l'aspetti ! :eek:

[repne scasb]

[a2000.1]

delusa da precedenti crivell... ehm ... esperienze ? :cool:

[repne scasb]

[a2000.1]

chi vive sperando ....

ma tu sei stata fortunata: la tua attesa finisce dopodomani sera !!! :winner:

[repne scasb]

[a2000.1]

con i parenti è incesto per definizione.

[Angus]

su un p4 2.53GHz con 384MB di ram e s.o. Win2000, il codice Java sottostante, compilato ed eseguito con la JDK Tiger (1.5.0), ha le seguenti prestazioni con n = 100000000 (cento milioni):

Time elapsed: 17875 ms
Primes found: 5761456
Cycles: 242570204
Avoidable cycles: 148331660
Efficiency: 0.38850006

n.b. il codice fa uso della classe java.util.BitSet, che implementa un array di bit, quindi l'algoritmo non lavora con gli interi. Una mia classe equivalente a BitSet ha prestazioni inferiori di circa il 40% :(


import java.util.BitSet;


public class BitEratostene {
public static void main(String[] args) {
if (args.length != 1) {
System.exit(1);
}
int n = Integer.parseInt(args[0]);
long start = System.currentTimeMillis();

// non c'è ottimizzazione sui pari e cose simili
// per semplicità l'array è inizializzato con tutti 0
// alla fine l'array conterrà 0 dove c'è un numero primo

// alloco l'array
BitSet primes = new BitSet(n + 1);
// ciclo esterno: f è il fattore preso in condiderazione
int cycles = 0, avoidableCycles = 0;
for (int f = primes.nextClearBit(2), fmax = (int) Math.sqrt(n);
f <= fmax;
f = primes.nextClearBit(f+1)) {
// se il fattore non è stato eliminato entra nel ciclo interno
if (!primes.get(f)) {
// ciclo interno: elimino tutti i multipli m del fattore f
// a partire da f^2, perchè tutti i precedenti sono stati già
// eliminati
for (int m = f * f; m <= n; m += f, cycles++) {
// se il bit è già a 1 si tratta di un ciclo inutile
if (primes.get(m)) avoidableCycles++;
primes.set(m);
}
}
}
long stop = System.currentTimeMillis();
// primes.length(): lunghezza dell'array
// primes.cardinaluty(): numero di bit a 1 nell'array
int tot = primes.length() - primes.cardinality() - 1;

System.out.println("Time elapsed: " + (stop - start) + " ms");
System.out.println("Primes found: " + tot);
System.out.println("Cycles: " + cycles);
System.out.println("Avoidable cycles: " + avoidableCycles);
System.out.println("Efficiency: " +
(cycles - avoidableCycles) / (float) cycles);
}

}

[a2000.1]

| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | .......

|<--- 8 bit --->|<--- 8 bit --->|<--- 8 bit --->| ...

[Angus]

Originariamente inviato da a2000.1

| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | .......

|<--- 8 bit --->|<--- 8 bit --->|<--- 8 bit --->| ...




immagino voglia essere un suggerimento... ci penso su mentre trangugio la focaccia coi pomodorini, olive nere e acciughe :oink:

[a2000.1]

bravo, comincia a risparmiare i 516 euri ! :D

[Angus]

Originariamente inviato da a2000.1
bravo, comincia a risparmiare i 516 euri ! :D

non ti dico quanto costa la focaccia qui in centro a Milano...
:cry:

[a2000.1]

ti stai strafogando da Luini ?

se mi aspetti arrivo :oink:

[Angus]

purtroppo no... sono in via Morigi incatenato alla mia "postazione di lavoro" :muro:
ma allora sei in zona milano?

[a2000.1]

sì, Milano SanManhattan :D

[Angus]

ah, quanto tempo è passato dall'esame di algebra...:mc:
che bello partizionare in base alle classi modulo...
ma crisbio non ricordo i dettagli! Sto ripassando la teoria su gugl...

[DanieleC88]

Ormai l'avete postato tutti, non potevo certo mancare io :)
Tenete conto che l'ho fatto di fretta, senza copiare codice altrui, e che sono un ignorante in C (si, vede, è un codice molto artigianale). Non deridetemi troppo, vi prego :)
Per il piacere di grandi e piccini vi ci metto anche dei commenti inutili.

/* by jmc, 7/12/04 */

#include <stdlib.h>
#include <stdio.h>

int main(int argc, char * argv[])
{
/* Dichiarazioni */
int * array = NULL;
int cmax;
int c;

if (argc <= 1) /* Abbiamo abbastanza argomenti? */
{
printf("Scrivi qualcosa, cazzo!\n");
return -1;
}

/* Allocazione */
cmax = atoi(argv[1]);
array = (int *) calloc(--cmax, sizeof(int));
/* Calcolo */
for (c = 4; c < (cmax + 1); c++)
array[c - 1] = (!(c % 2) || !(c % 3) || !(c % 5) || !(c % 7)) ? 0 : 1;
/* "Inizializzazione" */
array[0] = array[1] = array[2] = array[4] = array[6] = 1;

for (c = 0; c < cmax; c++)
if (array[c])
printf("%d\t", (c + 1));
printf("\n");
/* Fine */
free(array);

/* Nessun errore, fine! */
return 0;
}

[DanieleC88]

Che ne dite di farlo in assembly?

[Angus]

torno dalle vacanze e mi ritrovo la sfida ancora aperta... peccato non aver molto tempo da perderci su... :(

[repne scasb]

[Angus]

posta anche le performances/limiti!

[repne scasb]

[DanieleC88]

Mio dio, sei geniale. Compila anche con NAsm?

[repne scasb]

[repne scasb]

[repne scasb]

[DanieleC88]

Oooh, I've got an headache :muro:
:(

Scherzo, ma per me quello è arabo. Io ci stavo provando in NAsm, ma non sapevo nemmeno da dove cominciare per un calcolo simile, quindi è ancora tutto in stato embrionale. Proverò a trarre ispirazine dal tuo codice. :)

[NA01]

:eek: :cry:


ho riesumato il 3d per provare i risultati di ricerca di numeri primi con algoritmi diversi.
ero pronto per le prove e..... :eek: :doh:

e' scomparso il codice di repne scasb! :cry: :huh:

:banned:
che e' successo?


ciao

[Angus]

che e' successo?


vorrei saperlo anch'io...

[cionci]

Aveva lasciato il forum e cancellato tutti i suoi messaggi...

[71104]

non c'è modo (per te che sei modderz) di vedere i suoi vecchi messaggi? mi piacerebbe vedere quegli algoritmi...

[repne scasb]

#include <stdio.h>
#include <stdlib.h>

#define N_TABLE 48

void main(argc,argv)
int argc;
char *argv[];
{
int lim,i,j,k,l;
char *list;
int t[N_TABLE]={2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10};

if(argc!=2)
return;
lim=atoi(argv[1]);
if((lim<7)||((list=calloc(sizeof(char),lim+1))==NULL))
return;
for(k=0,i=11;i<=lim; )
{
list[i]=1;
i+=t[k++];
if(k==N_TABLE)
k=0;
}

printf("2 3 5 7 ");
for(k=0,i=11;i*i<=lim; )
{
if(list[i])
{
printf("%d ",i);
for(l=k,j=i*i;j<=lim; )
{
list[j]=0;
j+=i*t[l++];
if(l==N_TABLE)
l=0;
}
}
i+=t[k++];
if(k==N_TABLE)
k=0;
}

for(;i<=lim; )
{
if(list[i])
printf("%d ",i);
i+=t[k++];
if(k==N_TABLE)
k=0;
}
}


Ultima versione in linguaggio C da me inviata, mi sembra di ricordare che presentava una elevata efficienza nell'esecuzione, ma si puo' fare molto meglio.

[71104]

ehm, tanto che ci siamo, leggi pvt plz ;)

[LUVІ]

#include <stdio.h>
#include <stdlib.h>

#define N_TABLE 48

void main(argc,argv)
int argc;
char *argv[];
{
int lim,i,j,k,l;
char *list;
int t[N_TABLE]={2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10};

if(argc!=2)
return;
lim=atoi(argv[1]);
if((lim<7)||((list=calloc(sizeof(char),lim+1))==NULL))
return;
for(k=0,i=11;i<=lim; )
{
list[i]=1;
i+=t[k++];
if(k==N_TABLE)
k=0;
}

printf("2 3 5 7 ");
for(k=0,i=11;i*i<=lim; )
{
if(list[i])
{
printf("%d ",i);
for(l=k,j=i*i;j<=lim; )
{
list[j]=0;
j+=i*t[l++];
if(l==N_TABLE)
l=0;
}
}
i+=t[k++];
if(k==N_TABLE)
k=0;
}

for(;i<=lim; )
{
if(list[i])
printf("%d ",i);
i+=t[k++];
if(k==N_TABLE)
k=0;
}
}


Ultima versione in linguaggio C da me inviata, mi sembra di ricordare che presentava una elevata efficienza nell'esecuzione, ma si puo' fare molto meglio.

Quoto il codice e uppo; quasi quasi mi cimento anche io, è da aaaanni che non mi diverto con queste cosine. :)

LuVi

[Aries67]

...post e so che si può fare di meglio, ma questa è la mia soluzione per il crivello. Si può eliminare il calcolo della radice quadrata (utilizzando sqrt) e sicuramente è possibile qualche aggiustamento però non c'è una moltiplicazione neanche a pagarla...

Il codice conteneva errori e quindi l'ho rimosso...
Appena a posto lo ripubblicherò

;)