Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // This is the Sieve of Eratosthenes method: fastest method to find all the primes less than a number
- int countPrimes(int n) {
- if (n < 2)
- return 0;
- vector<bool> primes(n, true);
- primes[0] = primes[1] = false;
- int result = n - 2;
- for (int i = 2; i*i < n; ++i) {
- if (primes[i] == true) {
- int j = i;
- while (i*j < n) {
- if (primes[i*j] == true) {
- primes[i*j] = false;
- --result;
- }
- ++j;
- }
- }
- }
- return result;
- }
- // This function returns a bool saying if n is a primer number or not
- // Important to notice that if any divisor is not found before sqrt(n), no divisors will be found
- // Good practice: j*j < n faster than j < sqrt(n). Furthermore sqrt(n) would not return an integer.
- bool is_prime(int n) {
- for (int j = 2; j*j <= n; ++j) {
- if (n%j == 0) {
- return false;
- }
- }
- return true;
- }
- int countPrimes(int n) {
- int result = 0;
- for (int i = 2; i < n; ++i) {
- if (is_prime(i))
- ++result;
- }
- return result;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement