My C solutions in 13ms,use Sieve of Eratosthenes and only test 6n-1 and 6n+1


  • 2
    A
    // my sqrt
    unsigned short sq(unsigned int n){
        unsigned short root=0,i;
        unsigned int rem=0,divisor=0;
        for(i=0;i<16;++i) {
        	root<<=1;
        	rem=((rem<<2)|n>>30);
        	n<<=2;
        	divisor=root<<1|1;
        	if(divisor<=rem) {
        		rem-=divisor;
        		++root;
        	}
        }
        return root;
    }
    int countPrimes(int n) {
        if(n<3)return 0;
        else if(3==n)return 1;
        else if(n<6)return 2;
        else if(n<8)return 3;
        else {
        	unsigned char* dt[2];
        	int i,j,k,r;
        	const int n_6=n/6-1, // 6*x+5<=n-1
         		  n_8=(n-8)/6,   // 6*x+7<=n-1
        		  n_6_8=(n_6>>3)+1,
        		  i_max=((int)sq(n_8*6+7)-5)/6;
        	for(i=0;i<2;++i)dt[i]=(unsigned char*)calloc(n_6_8,sizeof(unsigned char));
        	if(n>25) {
        		for(i=0,k=5,r=7;i<=i_max;++i,k+=6,r+=6) {
        			for(j=(6*i+12)*i+5;j<=n_6;j+=k)
        				dt[0][j>>3]|=1<<(j&7);
        			for(j=(6*i+10)*i+3;j<=n_8;j+=k)
        				dt[1][j>>3]|=1<<(j&7);
        			for(j=(6*i+12)*i+5;j<=n_6;j+=r)
        				dt[0][j>>3]|=1<<(j&7);
        			for(j=(6*i+14)*i+7;j<=n_8;j+=r)
        				dt[1][j>>3]|=1<<(j&7);
        		}
        	}
        	r=2;
        	for(i=n_6_8-2;i>=0;--i) {
        		k=8;
        		j=dt[0][i];
        		while(j) {
        			j=j&(j-1);
        			--k;
        		}
        		r+=k;
        		k=8;
        		j=dt[1][i];
        		while(j) {
        			j=j&(j-1);
        			--k;
        		}
        		r+=k;
        	}
        	k=(n_6&7)+1;
        	j=dt[0][n_6_8-1];
        	while(j) {
        		j=j&(j-1);
        		--k;
        	}
        	r+=k;
        	k=(n_6&7)+(n_6==n_8?1:0);
        	j=dt[1][n_6_8-1];
        	while(j) {
        		j=j&(j-1);
        		--k;
        	}
        	r+=k;
        	for(i=0;i<2;++i)free(dt[i]);
        	return r;
        }
    }

  • 0
    S

    can you explain the logic behind your program.
    I understand the sieve of eratosthenes but this looked quite different.


  • 0
    S

    In 6 month time this code will be complete gibberish to yourself as well lol


  • 0
    Q

    thanks for your inspiration, just count odd numbers is really a brilliant idea!

    but as @sadboyzz pointed out. your code maybe too messed up. my below code use your ignoring even numbers idea, but much simpler, 10 lines, almost as efficient, 16ms, compared to 13ms.

    simple 16 ms,10 line C++ solution. 1.use new bool array 2. only traverse odd numbers 3.count and sieve at the same time


Log in to reply
 

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