Cod sursa(job #2069924)
| Utilizator | Data | 18 noiembrie 2017 22:55:35 | |
|---|---|---|---|
| Problema | Ciurul lui Eratosthenes | Scor | 20 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.5 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("ciur.in");
ofstream out("ciur.out");
long long n,d,v[200000000],i,j,Q,D,P;
int main()
{
in>>n; P=n/2; Q=P-1;
for (i=1;i<=n;i++) v[i]=i;
for (d=3;d*d<=n;d++)
{ D=d;
if (d%2==0) D=d/2;
for (j=3;j<=n;j++)
if ( v[j]%D==0 && v[j]!=D && v[j] && v[j]%2==1)
{
v[j]=0;
Q++;
}
}
out<<n-Q-1;
return 0;
}
