• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled bbescos  Jan 28th, 2019 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1.
2.
3.     // This is the Sieve of Eratosthenes method: fastest method to find all the primes less than a number
4.     int countPrimes(int n) {
5.         if (n < 2)
6.             return 0;
7.         vector<bool> primes(n, true);
8.         primes = primes = false;
9.         int result = n - 2;
10.         for (int i = 2; i*i < n; ++i) {
11.             if (primes[i] == true) {
12.                 int j = i;
13.                 while (i*j < n) {
14.                     if (primes[i*j] == true) {
15.                         primes[i*j] = false;
16.                         --result;
17.                     }
18.                     ++j;
19.                 }
20.             }
21.         }
22.         return result;
23.     }
24.
25.     // This function returns a bool saying if n is a primer number or not
26.     // Important to notice that if any divisor is not found before sqrt(n), no divisors will be found
27.     // Good practice: j*j < n faster than j < sqrt(n). Furthermore sqrt(n) would not return an integer.
28.     bool is_prime(int n) {
29.         for (int j = 2; j*j <= n; ++j) {
30.             if (n%j == 0) {
31.                 return false;
32.             }
33.         }
34.         return true;
35.     }
36.
37.     int countPrimes(int n) {
38.         int result = 0;
39.         for (int i = 2; i < n; ++i) {
40.             if (is_prime(i))
41.                 ++result;
42.         }
43.         return result;
44.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top