节约空间的筛素数方法
求不超过n的所有素数，比较好的算法是埃拉托斯特尼筛法：给出要筛数值的范围n，找出
以内的素数
。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。
这个算法非常快，但缺点是消耗内存，理论上n范围内的所有数都要保存在内存中。这个可以进行一个优化：每个数只要分配一位就可以了，毕竟我们只需知道这个数是否是素数。这里还可以进一步优化：我们只需保存所有奇数就行了（除2外的偶数都不是素数），因此，我们可以使用n/16的内存实现这个算法：
inline bool getBit(char* arr, size_t pos){return (arr[pos / 8] & (1 << pos % 8)) != 0;}inline void setBit(char* arr, size_t pos){arr[pos / 8] |= (1 << pos % 8);}void printPrimes(size_t n){if (n < 2)return;char* arr = new char[(n + 15)/16];memset(arr, 0, (n + 15)/16);//printf("2");size_t total = 1; //2for (size_t curNum=3; curNum <= n; curNum+=2){if (getBit(arr, curNum/2))continue;++total;//printf(" %lu", curNum);for (uint64 pos = (uint64)curNum*curNum/2; pos < n/2; pos += curNum){setBit(arr, pos);}}printf("\ntotal number: %lu\n", total);delete [] arr;}