Invece del setaccio di Eratostene ho deciso di postarti quest'altra tecnica basata
sul LEMMA DI FIBONACCI,il setaccio infatti ha bisogno di utilizzare un array di n
elementi come appoggio e non mi piace tanto (se n è grande non è il massimo).

------------------------------------------------------------------------------
LEMMA DI FIBONACCI

Sia n un intero (supponiamo positivo ma per i negativi prendiamo il modulo),
il PIU' PICCOLO dei fattori primi di n,chiamiamolo p(i),soddisfa la relazione:

p(i) <= parte_intera _inferiore(radice_quadrata(n))
------------------------------------------------------------------------------
Se ti interessa ti posto la dimostrazione,altrimenti fidati.
Il lemma in pratica ci dice che se c'è un fattore di n (e quindi n non è primo)
esso è minore o uguale alla parte intera inferiore della radice quadrata di n
altrimenti si contraddice il lemma (che però è dimostrato e quindi vero).Infatti
ammettendo per assurdo che prima della parte intera inferiore della radice non si trovino
fattori, e se ne trovi uno subito dopo,questo sarebbe il primo,contraddicendo
l'affermazione che il primo sia più piccolo della parte intera inf.....
Da cui il semplice algoritmo che controlla se tra quelli prima del suddetto limite
c'è un numero che divide esattamente n oppure no.
Nota che anche per n pari ad 1.000.000 ,l'algoritmo vien eseguito al più in 1000 passi circa
(solo se n è primo) quindi è abbastanza buono.




codice:
#include <stdio.h>

#define TRUE 1
#define FALSE 0

typedef unsigned char BOOL;

BOOL isPrime(int n);

main()
{
	int m,i;
	do
	{
		printf("Introduci un intero positivo:");
		scanf("%d",&m);
		if(m<1)
			printf("Un intero POSITIVO!!!\n");
	}while(m<1);
	printf("I numeri primi da 1 a %d:\n\n",m);
	for(i=1;i<=m;i++)
		if(isPrime(i))
			printf("%d ",i);
			
	//non far caso a queste due istruzioni
	fflush(stdin);
	getchar();

}

//Ritorna vero se n è primo e falso
//altrimenti
BOOL isPrime(int n)
{
	int p;
	int limit = (int)sqrt(n);
	for(p=2;p<=limit;p++)
		if(n % p == 0) //controlla se è divisibile
			return FALSE;
	return TRUE;
}