求小於一個整數的質數的個數的n個版本
輸入一個整數n，輸出不大於它的質數的個數。
這是一個經典的問題。不管用什麼算法，思路都是嵌套循環，對小於n的自然數判斷是否質數。
代碼不好貼，就截圖了。文末面有源碼鏈接。
基礎版
最笨的辦法就是按順序分別判斷：//基础版
int primeNum_0(int n)
{
int div;//试除变量
int count = 0;//质数个数
for (int i = 2; i <= n; ++i)
{
for (div = 2; div < i; ++div)
{
if (i % div == 0)//不是质数
break;
}
if (div == i)//质数
++count;
}
return count;
}
測試輸出：
There are 9592 prime numbers in 99999.
Completed with 1429 ms.
升級版
//升级版
int primeNum_1(int n)
{
int div, count = 0;
for (int i = 2; i <= n; ++i)
{
//试除上限为i的平方根取较大整数
int top = floor(sqrt(i)) + 1;
for (div = 2; div < top; ++div)
{
if (i % div == 0)
break;
}
if (div >= top)
++count;
}
return count;
}
這裡對比上面的基礎版，盡管代碼有些變化，但可以看出它們僅有的區別就是當試除i的數div大於√i時，就不再繼續試除，而判定i為質數。
這裡利用了數本身的性質：如果一個數i可以被不小於√i的整數整除，那麼得到的商一定是不大於√i的整數。因此，在試除到√i時便可以判定i是否為質數了。
這樣一步操作，使運算的次數大大減少。
測試輸出：
There are 9676 prime numbers in 99999.
Completed with 24 ms.
There are 665107 prime numbers in 9999999.
Completed with 5680 ms.
對於輸入99999，對比基礎版的超過1秒的運算時間，升級版只用了不到0.1秒。
升級改良版
在升級版的基礎上，還可以改進。
//升级改良版
int primeNum_2(int n)
{
int div, count = 1;//2直接算作质数
for (int i = 3; i <= n; i = i + 2)
{
//因为试除从3开始，2的试除单独提出来
if(i % 2 == 0)
continue;
int top = floor(sqrt(i)) + 1;
for (div = 3; div < top; div = div + 2)
{
if (i % div == 0)
break;
}
if (div >= top)
++count;
}
return count;
}
這個版本相對於升級版又有了一些改動：試除從3開始，每次步進2。因為從循環裡是3開始的，所以對於2的試除單獨放出來(減少避免在循環中增加條件判斷)，不影響性能。同時這樣3也無法正常計算了，索性把3也提前算上，count初始化為2。
這裡的原理也很簡單：任何大於2的偶數不可能是質數。為了應用這個原理，有了上面的改動，雖然代碼變得有些畸形，不過速度卻相對提升了接近一倍。
其實這裡還有個bug，當輸入1或者2的時候也會輸出有兩個質數。可以在循環外加上條件判斷，單獨處理，只是這樣代碼會不那麼美觀。事實上這個算法在設計上本身也很不完美，博主還沒有學過算法，很多不規範的地方請諒解。
測試輸出：
There are 9674 prime numbers in 99999.
Completed with 0 ms.
There are 665105 prime numbers in 9999999.
Completed with 2826 ms.
這裡99999的輸入已經可以在1毫秒之內解決了，9999999用了接近3秒，和升級版的5秒多相比有了不錯的提升。
從速度上來看，99999從20多毫秒提升到1毫秒，二十多倍，而9999999卻只是加快了兩倍左右，這或許和CPU的多任務機制有關，相關內容不怎麼熟悉，就不解釋了。因此用執行時間來反應算法速度並不很科學，或許用變量記錄最內層循環執行的次數會更好。
豪華版
//豪华版
int primeNum_3(int n)
{
int count = 1;
int maxSize;//最大存储质数的个数
//申请内存
if(MAX_SIZE < ceil(sqrt(n)))
maxSize = MAX_SIZE;
else
maxSize = (int)(sqrt(n));
int* primeNums = (int*)malloc((maxSize * sizeof(int)));
primeNums[0] = 2;//2先放进去
int size = 1;//当前存储的质数个数
int div, cur, top;
for (int i = 3; i <= n; ++i)
{
top = ceil(sqrt(i));//试除上限
cur = 0;//当前试除数在存储空间的位置
div = primeNums[cur];
while (i % div != 0)
{
if (div >= top)
{
if (size < maxSize)//判断存储空间是否已满
primeNums[size++] = i;//将质数加入存储数组
++count;
break;
}//找到质数
//若已试除到存储空间最后一个数，步进2
if (cur < size - 1)
div = primeNums[++cur];
else
div += 2;
}
}
free(primeNums);
return count;
}
還有一個可以利用的性質，對於正整數i，如果i 可以被div整除(div為小於i且大於2的非質數)，那麼i一定存在小於div的質數可以整除i，因為非質數div可以被分為若幹質數的乘積。
而我們判斷一個數是否是質數是從2開始去試除這個數(即使這個判斷被單獨列出)，而2是最小的質數，因此要判斷一個大於2的正整數i是否是質數，只需要判斷是否存在一個數k可以整除i，其中k是[2,√i]區間內的質數。
因此，我們可以建立一個質數存儲表。每當判斷出一個數是質數時，就把這個數加入表中。因為我們是從小到大開始判斷，所以這個表也是從小到大的。然後對於一個數i，只需用這個表中不大於√i的質數去試除i，如果最後一不大於√i的質數都無法整除i，那麼i是一個質數。
這個方法比上一種快一些，但消耗的空間也大得多。
測試程序
int main()
{
int n = 0;
scanf("%d", &n);
if(n < 2)
return 0;
int result, timeCount;//计时
if(n <= 100000)
{
timeCount = clock();
result = primeNum_0(n);
timeCount = clock() - timeCount;
printf("%d 个质数，基础版，%d 毫秒\n", result, timeCount);
}//数值太大基础版耗时太久
timeCount = clock();
result = primeNum_1(n);
timeCount = clock() - timeCount;
printf("%d 个质数，升级版，%d 毫秒\n", result, timeCount);
timeCount = clock();
result = primeNum_2(n);
timeCount = clock() - timeCount;
printf("%d 个质数，升级改良版，%d 毫秒\n", result, timeCount);
timeCount = clock();
result = primeNum_3(n);
timeCount = clock() - timeCount;
printf("%d 个质数，豪华版，%d 毫秒\n", result, timeCount);
//system("pause");
}