节约空间的筛素数方法(转)
求不超过n的所有素数,比较好的算法是埃拉托斯特尼筛法:给出要筛数值的范围n,找出\sqrt{n}以内的素数p_{1},p_{2},\dots,p_{k}。先用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; //2 for (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; }