求不超過n的所有素數，比較好的算法是埃拉托斯特尼篩法：給出要篩數值的范圍n，找出以內的素數。先用2去篩，即把2留下，把2的倍數剔除掉；再用下一個質數，也就是3篩，把3留下，把3的倍數剔除掉；接下去用下一個質數5篩，把5留下，把5的倍數剔除掉；不斷重復下去......。 這個算法非常快，但缺點是消耗內存，理論上n范圍內的所有數都要保存在內存中。這個可以進行一個優化：每個數只要分配一位就可以了，畢竟我們只需知道這個數是否是素數。這裡還可以進一步優化：我們只需保存所有奇數就行了（除2外的偶數都不是素數），因此，我們可以使用n/16的內存實現這個算法： [cpp] 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; } 在我的pc上求1億內的質數剛好花了1秒鐘，而只需分配6M多的內存就夠了。
