/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <iostream>
#include <cstdlib>
using namespace std;
void SieveOfEratosthenes(long int n)
{
int* prime;
prime = (int*)malloc(sizeof(int) * (n+1));
for (long int i = 0; i < n + 1; i++) {
prime[i] = 1;
}
long int c = 0;
long int p = 2;
while (p * p <= n) {
if (prime[p] == 1) {
for (long int i = p * p; i < n + 1; i += p) {
if(prime[i] == 1){
prime[i] = 0;
c++;
}
}
}
p += 1;
}
free(prime);
std::cout << "Number of primes <= " << n << ": " << (n - c - 1) << std::endl;
}
int main()
{
SieveOfEratosthenes(1000000000);
return 0;
}
