Cod sursa(job #622106)
Utilizator | Claudiu cocoshila | Data | 17 octombrie 2011 14:11:56 |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.54 kb |
#include<stdio.h>
const int N=1000000;
bool c[N];
int s;
int prim(int x)
{
int j;
if(x==2) return false;
else
if(x%2==0) return true;
for(j=3;j*j<=x;j+=2)
{
if(x%j==0)
{
return true;
break;
}
}
return false;
}
int main()
{
int i,j,n;
freopen("ciur.in","r",stdin);
freopen("ciur.out","w",stdout);
scanf("%d",&n);
for(i=2;i*i<=N;i++)
{
if(prim(i)==false)
for(j=i*i;j<=n;j+=i)
c[j]=true;
}
for(i=2;i*i<=N;i++)
if(c[i]==false)
s++;
printf("%d",s);
return 0;
}