TLE using vector but AC using array?


  • 0
    Z
    class Solution {
    public:
        int countPrimes(int n) {
            int primes[1000000];
            int size=1;
            if(n<=2) return 0;
            primes[0]=2;
            for(int i=3;i<n;i++){
                bool isPrime=true;
                for(int j=0;j<size&&primes[j]*primes[j]<=i;j++){
                    if(i%primes[j]==0){
                        isPrime=false;
                        break;
                    }
                }
                if(isPrime){
                    primes[size]=i;
                    size++;
                } 
            }
            return size;
        }
    };
    

    This code AC but if I use primes as a vector, TLE with input n=1500000;


  • 0
    L

Log in to reply
 

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