C++ O(n) solution 28ms


  • 0
    C
    #define N 2000000
    #define M 200000
    class Solution {
    public:
        bool visit[N] = {};
        int p[M] = {};
        int countPrimes(int n) {
            int res = 0;
            for(int i = 3; i < n; i+=2) {
                if(!visit[i]) {
                    p[res++] = i;
                }
                for(int j = 0; j < res && i*p[j] < n; j++) {
                    visit[i*p[j]] = true;
                    if(i % p[j] == 0) {
                        break;
                    }
                }
            }
            return res+(n>2?1:0);
        }
    };
    
    //if you consider 6n+1 and 6n-1, it may run even faster~

  • 1
    A

    Well, just want to tell you: sadly, it is not O(n).


  • 0
    O

    it's apparently not O(n) but if it can run in 28ms then whatever


Log in to reply
 

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