C 355ms solution sieve method


  • 0
    B
    int countPrimes(int n) {
        int *p = malloc(sizeof(int) * (n));
        for (int i = 1;i < n;i++)
            p[i] = 1;
        // memset(p , 1, sizeof(p));
        int ret = 0;
        int tmp;
        for (int i = 2;i < n;i++){
            if (p[i]){
                ret++;
                tmp = i + i;
                while(tmp < n){
                    p[tmp] = 0;
                    tmp += i;
                }
            }
        }
        free(p);
        return ret;
    }
    

Log in to reply
 

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