Cod sursa(job #1010606)
Utilizator | Alexandru Buicescu PsychoAlex | Data | 15 octombrie 2013 12:43:15 |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 30 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.99 kb |
#include <iostream>
#include <fstream>
std::ifstream fin("ciur.in");
std::ofstream fout("ciur.out");
long n, nr;
bool vec[2000001];
void citire()
{
fin>>n;
for(int i = 0; i < n; i+=2)
{
vec[i] = true;
}
}
bool isPrim(long p)
{
for(int i = 2; i*i <= p; i++)
{
if(p % i == 0)
{
return false;
}
}
return true;
}
void rezolvare()
{
nr++;
for(int i = 3; i < n; i++)
{
// std::cout<<i<<' '<<isPrim(i)<<'\n';
if(vec[i] == false)
{
if(isPrim(i))
{
nr++;
int j = i;
while(j < n)
{
vec[j] = true;
j += i;
}
}
}
}
fout<<nr<<'\n';
// std::cout<<'\n'<<nr<<'\n';
}
int main()
{
citire();
rezolvare();
return 0;
}