Cod sursa(job #2069924)

Utilizator RaduIonescuRadu Ionescu RaduIonescu 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;
}