C++ code using prime number,4ms


  • 0
    C
    class Solution {
        bool prime[1000];
        vector<int>a;
        void getPrimeTable(){
            int size= 1000;
    	    memset(prime, 0, sizeof(bool) * size);
    	    for (int i = 2; i < size; i++){
    		    for (int j = i * 2; j < size; j += i)
        			prime[j] = true;
    	    }
    	    for (int i = 2; i < size; i++){
    		    if (!prime[i]) a.push_back(i);
    	    }
        }
    public:
        Solution(){
            getPrimeTable();
        }
        bool isPerfectSquare(int num) {
            if(num<1) return false;
    
    	    for (int i = 0; i < a.size()&&num!=1; i++){
    	    	int fact = a[i] * a[i];
    	    	while (num){
    	    		if (num % fact != 0)
    		    		break;
    		    	num /= fact;
    		    }
    	    }
    	    if (num==1) 
    	        return true;
    	    return false;
        }
    };
    

  • 0

    Fails for example 1018081.


Log in to reply
 

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