Simple 16 ms,10 line C++ solution. 1.use new bool array 2. only traverse odd numbers 3.count and sieve at the same time


  • 24
    Q
    1. use new bool array. 2. only traverse odd numbers. 3. count and sieve at the same time.

    trick 1, thanks to 27ms,16 lines, C++ solution

    trick 2, for the inspiration, thanks to my C solutions in 13ms,use Sieve of Eratosthenes and only test 6n-1 and 6n+1

    trick 3, thanks to my C solutions in 44ms, time nearly O(n), and space nearly O(n) and my easy one round c++ code

    int countPrimes(int n) {
    	if (n <= 2) return 0;
    	int res=n>>1, m=sqrt(n-1); // intilize res to n/2, removes all even number(not 2) and 1
    	bool *table=new bool[n];
    	for(int i=3,j,step;i<=m;i+=2)
    		if(!table[i]) { // i is an odd prime
    			for(step=i<<1, j=i*i;j<n;j+=step) // step=i*2, ignore even numbers
    			if(!table[j]) { table[j]=1; --res; }
    		}
    	delete []table;
    	return res;
    }
    

  • 0
    H

    Can you explain "sqrt(n-1)"? And I think "res = n >>1" because the algorithm skips even numbers, so the max numbers of prime will be n/2, can you confirm that please? Thanks!


  • 0
    Q

    for sqrt part, in hint 3 of the problem desciption ([Count Primes][1]), "Therefore, we only need to consider factors up to √n because, if n is divisible by some number p, then n = p × q and since p ≤ q, we could derive that p ≤ √n."
    [1]: https://leetcode.com/problems/count-primes/


  • 0

    @qeatzy your array is not even initialized.


  • 0

    Thank you for your share.
    As @leo-lai-944 pointed out, your bool array is not initialized and you'll get Wrong Answer.
    And what I want to say is that using unsigned char and bit manipulation can save much time and 7/8 space.
    Here is a 9ms version:

    class Solution {
    public:
        int countPrimes(int n)
        {
            if (n <= 2) return 0;
            int ans = n >> 1, m = sqrt(n - 1); // intilize res to n/2, removes all even number(not 2) and 1
            unsigned char *table = new unsigned char[n / 8 + 1];
            memset(table, 0xff, n / 8 + 1);
            for (int i = 3, j, step; i <= m; i += 2) {
                if (table[i / 8] & (1 << (i % 8))) { // i is an odd prime
                    for (step = i * 2, j = i*i; j < n; j += step) { // step=i*2, ignore even numbers
                        if (table[j / 8] & (1 << (j % 8))) {
                            table[j / 8] ^= (1 << (j % 8)); // flip bit
                            --ans;
                        }
                    }
                }
            }
            delete[] table;
            return ans;
        }
    };
    

Log in to reply
 

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