Cod sursa(job #1285058)
Utilizator | Stephen Berg BlackBird_v.1.0 | Data | 7 decembrie 2014 01:20:46 |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 30 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.43 kb |
#include <bits/stdc++.h>
using namespace std;
int Ld[2000013],Q[2000013],sol(0),n,sf(0);
int main()
{
ifstream cin("ciur.in");
ofstream cout("ciur.out");
cin>>n;
for (int i=2;i<=n;++i)
{
if (Ld[i]==0)
{
Ld[i]=i;
Q[++sf]=i;
}
for (int j=1;j<=sf && i*Q[j]<=n && Q[j]<=Ld[i] ; ++j)
Ld[i*Q[j]]=Q[j];
}
for (int i=2;i<=n;++i)
if (Ld[i]==i) ++sol;
cout<<sol;
return 0;
}