My accepted c++ code, 128ms


  • 3

    Give a number N, it goes form 2 to n - 1, and remove all the multiples of N.

    For example, when n is 8:

    N=2: 2(×),3,4(×),5,6(×),7

    N=3: 2(×),3(×),4(×),5,6(×),7

    N=4: 2(×),3(×),4(×),5,6(×),7

    N=5: 2(×),3(×),4(×),5(×),6(×),7

    N=6: 2(×),3(×),4(×),5(×),6(×),7

    N=7: 2(×),3(×),4(×),5(×),6(×),7(×)

    class Solution {
    public:
        int countPrimes(int n) {
    		if (n < 2)
    			return 0;
    		std::vector<int> flag(n - 2, 1);
    		int res = 0;
    		for (int i = 0; i < n - 2; ++i)
    			if (flag[i]) {
    				++res;
    				for (int j = i; j < n - 2; j += i + 2)
    					flag[j] = 0;
    			}
    		return res;
        }
    };
    

    Update:

    class Solution {
    public:
        int countPrimes(int n) {
    		if (n <= 2)
    			return 0;
    		std::vector<int> flag(n, 1);
    		int res = 1, sqr = std::sqrt(static_cast<double>(n)), i = 3;
    		for (; i <= sqr; i += 2)
    			if (flag[i]) {
    				++res;
    				for (int j = i * i; j < n; j += i)
    					flag[j] = 0;
    			}
    		for (; i < n; i += 2)
    			res += flag[i];
    		return res;
        }
    };

  • 0
    Q

    "std::vector<int> flag(n - 2, 1);"meas?


  • 0
    Y

    it means flag has (n-2) int variables, and every variable is set value 1.


Log in to reply
 

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