[joebin]

作者: clout

謝謝兩位

雖然還看不大懂，但至少知道要往哪個方向去想了

那我用學生的語言解說好了^^"



首先要質數的定義是:
除了自己和1外無其他的因數(1除外)


再來是談論到因數問題:
若正整數N在根號N中只找到1這個因數,則N為質數(1除外)

原因:
設N.n.m為一自然數,且n * m = N,則n.m為N的因數(註:n >= m)
另設一數k,使其 k * k = N,則就n.m.k的大小而言,n >= k >= m
既然n * m = N,且k * k = N,那在小於或等於k的自然數中必能找到m
所以~若正整數N在根號N中只找到1這個因數,則N為質數(1除外)


由此想法來建構一程式

#include<iostream>
using namespace std;
int main(){
  int i,n,N,t;
  cin >>N;     //輸入你所要求質數的最高上限數,例如樓主所發問的60
  for(n=2;n<=N;n++){
    t=1;    //判斷n是否在2~根號n中尚有其他因數存在
    for(i=2;i*i<=n;i++)//若正整數n在根號n中只找到1這個因數,則n為質數
      if(n%i==0){
        t=0;
        break;
    }
    if(t==1) cout <<n<<endl;
  }
  return 0;
}

不知這樣的解說夠不夠清晰^^"