Count Primes

 1 int ary[1500005];
 2 class Solution {
 3 public:
 4     int countPrimes(int n) {
 5         int i,j;
 6         memset(ary,0,sizeof(ary));
 7         int m=sqrt(n)+1;
 8         for(i=2;i<m;i++)
 9         {
10             for(j=i;j<=n/i;j++)
11                 ary[i*j]=1;
12         }
13         int tot=0;
14         for(i=2;i<n;i++)
15         {
16             if(ary[i]==0)tot++;
17         }
18         return tot;
19     }
20 };

View Code

使用素数筛选法，保证在n(1/2+1/3+...1/sqrt(n))=nlog(n)时间内完成筛选，此题的难度在于空间复杂度，若是32M内存可以开16000000的Int数组，但是此题只能开5000000的内存，最大的数据是1500000；所以需要先问清楚数据范围