（1）求某個數n的素數，只需要判斷n 是否可以被2~sqrt(n)之間的數整除（包括2；如果sqrt（n）是整數，也包括它）。如果沒有被整除的，則是素數。
為什麽是到sqrt(n)，而不是取n下所有的數？這是因為，對於壹個數n來說，如果它有壹個非1 和非它本身的因子，那麽n必然有兩個因子，其中的壹個較小的因子，假定這個因子為m，它的取值範圍必定在1<m<=sqrt(n)。當且僅當這兩個因子相等的時候，取上面的等號。
如果妳在（1,sqrt(n)]找不到n的整數因子，妳壹定也不會在[sqrt(n),n)中找到n的整數因子。
（2）在（1,sqrt(n)]中，沒有必要用每壹個整數去試試是否能整除n。而是只用這個範圍之間的素數就可以了。因為任何壹個和數都可以分解為幾個素數的積。因此，在計算這種“求小於n的所有的素數”問題時，就有必要存儲下來已經計算出來的素數，可以減少以後進行%運算的次數。當n很大的時候，這種方法就顯示出優勢了，只是要多去開銷壹些內存空間。
壹句話，用(1,sqrt(n)]之間的素數去判斷壹個數n是否為素數。
代碼如下：
#include "stdafx.h"
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
int num = 100; //求num以下所有的素數
int i,j,i_prime = 0;
int primevector[50] = {0}; //用於存儲已經計算出來的素數,要用足夠大的空間來存儲所有的素數,對於100來說,50已經足夠了
//首先在primevector中記錄下前兩個素數2 , 3, i_prime是此數組中質數的個數
primevector[i_prime++] = 2;
primevector[i_prime++] = 3;
for(i=4;i<num;i++) //分別計算i 是不是素數
{
bool isprime = true;
float ftemp = sqrt(i);
//判斷 i 是否為素數
for(j=0;primevector[j] <= ftemp;j++)
{
if(i % primevector[j] == 0)
{
isprime = false;
break;
}
}
//如果 i 是素數，則保存到primevector之中
if(isprime)
primevector[i_prime++] = i;
}
//輸出所有的素數
for(i = 0;i<i_prime;i++)
cout<<primevector[i]<<' ';
cout<<endl;
return 0;
}