Accepted C Solution implement sieve of Eratosthenes


  • 0
    R
    int countPrimes(int n) {
    	bool *pb = calloc(n-1,sizeof(bool));
        
    	int ret_c=0;
    	// idx 0 represent 2
    	int idx=0;
    	int pend=n-2;
    	while(idx<pend){
    		if(0==pb[idx]){
    			++ret_c;
    			int op=idx;
    			while(op<pend){
    				pb[op]=1;
    				op+=(idx+2);
    			}
    		} 
    		++idx;
    	}
    	free(pb);
    	return ret_c;
    }
    

    I just read the wiki and wrote the code above.wiki explains much more better than me~
    http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes


Log in to reply
 

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