素数
位保存
class Solution
{public:int countPrimes(int n){if (n <= 2)return 0;int i, j;int pi = 0;int flag[n / 3 + 1];memset(flag, 0, sizeof(flag));for (i = 2; i < n; i++){if (!((flag[i >> 5] >> (i & 0x1f)) & 1)){// cout << i << ":";pi++;for (j = i; j < n; j += i){// cout << j << " ";flag[j >> 5] |= (1 << (j & 0x1f));}// cout << endl;}}return pi;}
};