[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

Domani quando ho tempo lo faccio

CIao e grazie per il nuovo intrattenimento

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

#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.
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.
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




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




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

[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

7 istruzioni
PIII 350MHz
VBA
1000000 (un milione)

tempo di calcolo = 0.24 s

[VICIUS]

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

tempo di calcolo = 0.24 s

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

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

[VICIUS]

Originariamente inviato da AnonimoVeneziano
Sei un coniglio

Zitto tu.

[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]