Why the code exceeds time limits?


  • 0
    Y
    class Solution {
    public:
        int countPrimes(int n) {
            if(n<=1) return 0;
            vector<bool> flag(n,true);
            for(int index = 2; index<sqrt(n);index++){
                if(flag[index]){
                    for(int j=index*index;j<n;j+=index){
                        flag[j]=false;
                    }
                }
            }
            int sum;
            for(int i=2;i<n;i++){
                sum += (flag[i])?1:0;
            }
            return sum;
        }
    };

  • 0
    M

    Look for a much more efficient way to solve the problem. Take the hints and references into consideration. Feel free to reach out to me by replying to this post, if you face any issues.


  • 0
    Y

    I have created a bool vector using the vector<bool>. It seems that this procedure will cost a lot of time. I have used an array instead. Now the code works. Thanks for your help.


  • 0
    T
    index < sqrt(n)
    

    This will call sqrt() function at every single iteration, which is expensive.

    Try this instead

    index * index < n
    

    Or simply calculate it once, and store it in a variable.


Log in to reply
 

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