Conteggio numeri primi

1990 – Maturità scientifica sperimentale – Indirizzo matematico-informatico

Si scriva un programma che produca i numeri primi inferiori a 100.000.

Si calcoli quanti sono i numeri primi che cadono in ciascuno dei seguenti intervalli

• 1 – 1.000
• 1.001 – 2.000
• 2.001 – 3.000
• …
• 99.001 – 100.000.

#include 
#include 
using namespace std;
 
bool primo(long x)
{
	long ultimo=(long)sqrt(x);
	
	for(long i=2; i <= ultimo; i++)
	    if(x%i == 0)
	        return false;
	return true;        
}

int main()
{     
    long minimo =2;
	long massimo=1000;
	
	for(int i=1; i <= 10; i++)
	{
		long quanti=0;		
	    for(long N=minimo; N <= massimo; N++)
            if(primo(N))			
            {
				quanti++;
	            cout << N << " ";  // facoltativo...
		    }
		cout << endl << endl << quanti << endl << endl;    
		
		minimo =massimo+1;
		massimo=massimo+1000;
    }
    return 0;
}