Share C solution in 33ms


  • 0
    B

    My ideas is like many people( http://www.geeksforgeeks.org/sieve-of-eratosthenes/) :
    If you get a error :
    ... index 1000 out of bounds for type 'char [1000]'....
    that means the size of array does not enough. After I try many time, I found the maximum size of array for this problem is array[1800000];

    int countPrimes(int n) {
    
    	char array[1800000];
    	memset(array,0,sizeof(array));
    
    	int i,j;
    	int count = 0;
    
    	if(n <= 2){
    		return 0;
    	}
    	for( i = 2; i < n; i++){
                if(array[i] == 0){
                    for( j = i * 2; j < n; j =  j + i){
                        array[j] = 1;
                    }
                }
            }
        count = 0;
        for(i = 2; i < n; i++){
                if(array[i] == 0 ) count++;
        }
    
       // printf("count: %d \n",count );
        return count;
    
    }
    

Log in to reply
 

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