12ms c++ solution


  • 13
    A

    Here are my 12 ms and 16ms with less space solutions

    I saw there are submission within 10ms. Can anyone share that? Thanks!

    12 ms:

    Here notPrime[i] refer to the number a = 2* i + 1, so the marking process starts from a^2 which is 2i(i+1) back to index

    int countPrimes(int n) {
        if(--n < 2) return 0;
        int m = (n + 1)/2, count = m, k, u = (sqrt(n) - 1)/2;
        bool notPrime[m] = {0};
        
        for(int i = 1; i <= u;i++)
            if(!notPrime[i])
              for(k = (i+ 1)*2*i; k < m;k += i*2 + 1)
                  if (!notPrime[k])
                  {
                      notPrime[k] = true;
                      count--;
                  }
        return count;
    }
    

    16 ms with less space:

    almost same as above just squeeze 8 bit into a char

    int countPrimes(int n) {
        if(--n < 2) return 0;
        char notPrime[(n + 1)/16+1] = {0};
        int count = (n+1)/2, k,  u = (sqrt(n) - 1)/2;
        
        for(int i = 1; i <= u;i++)
            if(!(notPrime[i>>3] & (1<<(i&7))))
              for(k = 2*i*(i + 1); k < (n + 1)/2;k += 2* i + 1)
                  if (!(notPrime[k>>3] & (1<<(k&7))))
                  {
                      notPrime[k>>3] |= (1<<(k&7));
                      count--;
                  }
        return count;
    }

  • 1
    K

    really really brilliant! how can you come up with this idea? Can you explain "m = (n + 1)/2, count = m" and "k = (i+ 1)2i; k < m;k += i*2 + 1"?


  • 0
    A

    Oh I just count the odd number and skip all even numbers. I ignore 1 since I ignored 2 as well. (So do nothing with 1 and it will be correct)

    As for "m = (n + 1)/2, count = m":

    Well that is how many odd number candidate you have in total....I counted it by subtract the one the proof not prime.

    For "k = (i+ 1)2i; k < m;k += i*2 + 1"

    Well I explained that before: When I encounter prime number a, I marked all the numbers starting from aa with step 2a. Remember here a is stored in i = (a-1)/2. So aa becomes (i+1)2i


  • 0
    P
    This post is deleted!

  • 0
    G

    hey bro, I just input the 9800000 as a testcase, and then the runtime is N/A :(


  • 0
    W

    This solutions should not really be accepted as it used non-standard extensions of dynamic arrays.


Log in to reply
 

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