C語言！！程式問題！

Question

用迴圈設計程式，找出2~100中的質數，每印5個就換行!!

Answer 1

//Power by Microsoft Visual Studio 2005
//可以使用 Dev-C++ 編譯此程式
#include
#include
#include
#include
#define blnTrue EOF
#define blnFalse 0
int main(int argc,char *argv[]){
//=====START=====//
int check_prime(int);
void display_factor(int);
int nNumber[99],i,j,k;
for(i=0,j=2,k=0;i<99;i++,j++){
nNumber[i]=j;
if(check_prime(nNumber[i])){
printf(" %2d",nNumber[i]);
k++;
if(k>4){
printf("\n");
k=0;
}
}
}
printf("\n");
//=====END=====//
system("PAUSE");
return 0;
}
int check_prime(int number){//Check number
int i,retBoolean=blnTrue;
//1 is True, 0 is False
for(i=2;i<=(int)sqrt(number);i++){
if((number%i)==0){
retBoolean=blnFalse;//false
break;
}
}
return retBoolean;//return boolean value
}

2006-07-25 01:59:56 補充：
以下網路上可參考的資料…埃拉托色尼篩法 (求質數法)良葛格學習筆記 網站：http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/EratosthenesPrime.htm

2006-07-25 02:08:12 補充：
以下網路上可參考的資料…
埃拉托色尼篩法 (求質數法)
埃拉托色尼篩法不適合求 10000以上 大型數字，大數要用到梅森數計算

良葛格學習筆記 網站：
http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/EratosthenesPrime.htm

Answer 2

#include
#include
int a(int);
int main()
{
int i;
for(i=2;i<=100;i++)
if(a(i))
printf("%3d",i);
printf("\n");

system("pause");
return 0;
}

int a(int n)
{
int i;
for(i=2;i<=n-1;i++)
if(n%i==0)
return 0;
return 1;
}

Answer 3

用The Sieve of Eratosthenes 的方法寫的程式是最快的。
常然，還可以再用其它方法再加速！
如：去2、(去3、)、Fit in cache 等。
最終的速度會快到小綿羊法無法想像的地步！

22年前，我用小綿羊法在Apple][ BASIC 裡寫，算到5000，花了約8小時！後來用了The Sieve of Eratosthenes 法，在加上〝去2〞加速，只花了 48 秒！
後來在80286-8上用 Turbo-Pascal 寫，算到 3000的樣子。大約是 3分鐘比不到1秒。

當然，只要算到200，綿羊法既簡單，速度也不會太慢。不失為本題的優良做法。

2006-07-25 21:31:38 補充：
我用The Sieve of Eratosthenes寫過1百萬以上的喔! 效果還是相當好! 把分界點設在 1萬, 太小了!! 286-16時就輕易算到 13萬了!

The Sieve of Eratosthenes 法的缺點是耗 RAM。但以現代動輒512M以上RAM的電腦而言, 用個400M要算到400*1024*1024*2=838860800=8.3億而言, 不難! 要再 * 8 = 67.1億也不會太難, 速度也不會降多少。

不過, 再大上去, 就不能用這個演算法了!