Cod sursa(job #357849)

Utilizator NemultumituMatei Ionita Nemultumitu Data 20 octombrie 2009 21:01:28
Problema Ciurul lui Eratosthenes Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.35 kb
Raporteaza aceasta sursa 
#include <cstdio>
bool prim[2000001];
int cnt;
int n;

int main()
{
	freopen ("ciur.in","r",stdin);
	freopen ("ciur.out","w",stdout);
	scanf("%d",&n);
	int i;
	for (i=2;i*i<=n;++i)
		if (!prim[i])
		{
			for (int j=i*i;j<=n;j+=i)
				prim[j]=1;
			cnt++;
		}
	for (;i<=n;++i)
		if (!prim[i])
			cnt++;
	printf("%d",cnt);
	return 0;
}