204. Count Primes - CPP - Solution


  • 0
    Y
    // 204. Count Primes
    // https://leetcode.com/problems/count-primes/
    // https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    #include <iostream>
    #include <vector> // required for vector container
    #include <cmath> // required for sqrt() function
    #include <algorithm> // required for count() function
    using namespace std;
    class Solution {
    public:
    	int countPrimes(const int& n) {
    		int result = 0;
    		vector<bool> prime(n, true);
    		prime[0] = false;
    		prime[1] = false;
    		for (int i = 2; i < sqrt(n); ++i) {
    			if (prime[i]) {
    				for (int j = i * i; j < n; j += i) {
    					prime[j] = false;
    				}
    			}
    		}
    		result = count(prime.begin(), prime.end(), true);
    		return result;
    	}
    };
    int main(int argc, const char** argv) {
    	Solution solution;
    	int n = 1500000;
    	cout << solution.countPrimes(n) << '\n';
    	getchar();
    	return 0;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.