Description:
Count the number of prime numbers less than a non-negative number, n.
算法: Sieve of Eeatosthese; 这个在之前的应用密码学里面学过,是在large n 里面找prime的算法, 一个数组标记是不是prime, 从2开始,如果是prime, 那么就将所有该数的
倍数标记为not prime, 怎么高效地除去所有这个数的倍数呢? 首先第一个倍数肯定是 i * i, 因为前面的倍数已经被mark为not prime了。 然后每次 i*i + i必定都是i的倍数, 所以是有一定规律可循的,不用一个个去去除。 这个是重点。
class Solution {
public:
int countPrimes(int n) {
//corner case
if (n < 2) return 0;
int rst = n-2;
//must use heap to store M, since M may be very large, and will get out the bound of stack.
int *M = new int[n];
for (int i = 0; i < n; i++) {
M[i] = 0;
}
M[0] = -1;
for (int i = 2; i * i < n; i++) {
if (M[i-1] != -1) {//is prime
int j = i*i;
for (; j < n; j += i) {
if (M[j-1] != -1) {
M[j-1] = -1;
rst--;
}
}
}
}
delete [] M;
return rst;
}
};
No comments:
Post a Comment