Fastest solution in C(20ms), using Bit Manipulation, less space !!!


  • 0
    B
    #define M 5000000
    char z[8] = { 1, 2, 4, 8, 16, 32, 64, 128 };
    char e[M/8];
    int countPrimes(int n) {
        int i,k,m,c;
        c = n>=3;
        n>>=1;
        for (i = 1; i < n; i++)
    		if (!(e[i >> 3] & z[i & 7]) && ++c)
    			for (k = (i << 1) + 1, m = i + k; m < n; e[m >> 3] |= z[m & 7], m += k);
        return c;
    }

  • 0

    Shifting on the fly instead of using z seems to consistently improve it from 24ms to 20ms.


  • 0
    B

    Really? I tried it before, but it is also 24ms.....


  • 0

    Yes, I tried each multiple times.

    Just to be sure we're talking about the same:

    #define M 5000000
    char e[M/8];
    int countPrimes(int n) {
        int i,k,m,c;
        c = n>=3;
        n>>=1;
        for (i = 1; i < n; i++)
            if (!(e[i >> 3] & (1 << (i & 7))) && ++c)
                for (k = (i << 1) + 1, m = i + k; m < n; e[m >> 3] |= (1 << (m & 7)), m += k);
        return c;
    }

  • 0
    B

    yes, the same code.I tried it serveral times just now and got some 20ms and 24ms. you are right. :-D


Log in to reply
 

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