### 問題描述 從2開始到n-1都不能整除則為素數。 ### 優化 1. 從2到sqrt(n)不能整除就可以 1. ?通過對被2、3和5整除的特殊檢驗，避免了近3/4的開方運算，其次，只考慮奇數作為可能的因子，在剩余的數中避免了大約一半的整除檢驗（注意一點，2，3，5本身也是素數）（If( n%2 == 0 ) return (n==2); //能被2整除且不是2本身的不是素數） 1. 用乘法運算代替開方運算 ~~~ int prime(int n) { if(n%2==0)return (n==2); if(n%3==0)return (n==3); if(n%5==0)return (n==5); for(int i=7; i*i<=n; i+=2) if(n%i==0)return 0; return 1; } ~~~ ### 簡單的埃氏篩法 實現簡單的埃氏篩法（Sieve of Eratosthenes）來計算所有小于n的素數。這個程序的主要數據結構是一個n比特的數組，初始值都為真。每發現一個素數時，數組中所有這個素數的倍數就設置為假。下一個素數就是數組中下一個為真的比特。 ### 解析 下面的C程序實現了埃氏篩法來計算所有小于n的素數。其基本數據結構是n比特數組x，初始值全部為1。每發現一個素數，數組中所有它的倍數都設為0。下一個素數就是數組中的下一個取值為1的比特位。 ~~~ #include <iostream> using namespace std; int main( ){ int i, p, n; char x[100001]; ?n = 100000; for (i = 1; i <= n; i++) x[i] = 1; x[1] = 0; //1不是素數 p = 2; //第一個素數 while (p <= n){ cout<<p<<" "; for (i = 2*p; i <= n; i = i+p) x[i] = 0; do p++; while (x[p] == 0); //得到第一個標記為1的數，為素數 } } ~~~ **轉載請注明出處**：[http://blog.csdn.net/utimes/article/details/8863999](http://blog.csdn.net/utimes/article/details/8863999)