尋找 1 到指定正整數之間所有的質數

程式要求:

一個質數是除了 1 及它自己之外沒有其它數可以整除它的數, 請撰寫一個函式 isPrime() 來判斷傳進去的參數是否為一質數。 並寫一個主程式運用這個 isPrime() 函式來判斷自 1 到任意指定正整數之間哪些整數是質數, 將它們列印在螢幕上, 計算總共有幾個? 它們的和是多少?

提示:

本程式最主要讓同學練習

  1. 適當變數型態的使用
  2. 迴圈
  3. 條件測試敘述
  4. 函式

的整合應用, 在測試一整數是否為質數時, 我們可以採用最"暴力"的方式來做, 你只需要一個一個地測試所有小於它的整數, 看看是不是可以整除它, 如果可以整除的話, 就表示它不是一個質數, 如果全部測試完畢之後沒有任何一個數可以整除, 那就是質數了。

請注意:

  1. 能夠處理的數字區間要夠大
  2. 請問這個程式處理 1 到 50000 在你的機器上大概要花多少時間? 你確定是 CPU 運算的時間嗎? 你試看看不要列印的話會不會快一點? 那麼你能不能預估 1 到 100000 大概要多少時間?

範例執行程式

程式設計課程 首頁
by Pei-yih Ting
E-mail: pyting@cs.ntou.edu.tw