count Primes Algorithm
In mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number X. It is denoted by π(x) proof of the prime number theorem not use the zeta function or complex analysis were found around 1948 by Atle Selberg and by Paul Erdős (for the most part independently). The prime number theorem was first proved in 1896 by Jacques Hadamard and by Charles de la Vallée Poussin independently, use property of the Riemann zeta function introduced by Riemann in 1859.where li is the logarithmic integral function.
/**
* Count the number of prime numbers less than a non-negative number, n.
*/
#include <iostream>
#include <vector>
#include <cmath>
int countPrimes(int n) {
if ( n <= 2) {
return 0;
}
int x = std::sqrt(n);
std::vector<bool> soe(n, false);
soe[1] = true;
for ( int i = 2; i <= x ; ++i ) {
if (soe[i] == false ) {
for (int j = i * i; j < n; j+=i) {
soe[j] = true;
}
}
}
int count = 0;
for ( int i = 2; i < n; ++i ) {
if(soe[i] == false) {
++count;
}
}
return count;
}
int main() {
std::cout << "Enter a non negative integer:" ;
int n;
std::cin >> n;
std::cout << "Number of primes less than " << n << " are " << countPrimes(n) << std::endl;
return 0;
}
