C++求素数问题

Question

/第七行中如果写成：for(m=1;m<=100;m=m+2)然后底下删去十一和十二行， 就可以输出除2外所有素数/
//那么如果要输出加上2的素数，我的这个程序错在哪（输出结果是2、3交替不停输出，都看不清

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int m,n,k;
    for(m=1;m<=100;m=m+1)//7
    {   bool prime=true;
        k=int(sqrt(float(m)));
        for(n=2;n<=k;++n)
        {if (m=2)//11
        break;//12
        else if(m%n==0)
        {prime=false;
        break;}
        }
        if (prime==true)
            cout<<m<<endl;

    }
    return 0;
}

Answer 1

錯誤在哪兒？

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int m,n,k;

    for (m=1; m<=100; m++) {

        bool prime = true;

        k = int(sqrt(float(m)));

        for (n=2; n<=k; n++) {
            if (m=2) { // 問題在此, 應改為 if (m==2)
                break;  
            }
            else if (m%n==0) {
                prime = false;
                break;
            }
        }

        if (prime==true) {
            cout << m << endl;
        }
    }

    return 0;
}

該行的錯誤會造成第一個印出的值為 1, 之後 2, 3 交錯.

為什麼呢？首先, m==1 的時候不會進去內層 for loop 但此時的 prime 是 true, 所以你會印出 1.

再來當 m==2 和 m==3 的時候是正常的, 兩者皆不會進入內層 for loop, 然後都會被印出.

接著當 m==4 的時候, 進入了內層 for loop, 但在 if (m=2) 這一步會讓 m 被設成 2, 且離開迴圈, 此時的 prime 仍然為 true 導致 2 重複被印出.

接著 m 再下一次迴圈會成為 3 (2+1), 此時 3 重複被印出.

接著你我都懂了, m==4 會讓一切陷入不可自拔的循環.

解決錯誤

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int m,n,k;

    for (m=2; m<=100; m++) {

        bool prime = true;

        k = int(sqrt(float(m)));

        for (n=2; n<=k; n++) {
            if (m==2) {
                break;  
            }
            else if (m%n==0) {
                prime = false;
                break;
            }
        }

        if (prime==true) {
            cout << m << endl;
        }
    }

    return 0;
}

很簡單, 首先將 m=2 改正為 m==2, 其次為了避免 1 被印出, 我建議外層的 for 直接從 2 開始走就好.

其他建議

1. 代碼的排版很重要, 會影響可讀性, 建議有自己一套邏輯, 盡量排得好看

   • 建議層次要分明(內層的 block 就要記得縮排)

   • 代碼別太壅擠

   • 我個人建議即便是單行的 if/else/for 都加上 {}, 統一, 好讀且不容易出問題

2. 可以嘗試抽出寫 function

3. 下次遇到錯誤可以自己模擬電腦跑個兩三次 loop 很容易抓到問題

---

我回答過的問題: Python-QA

Answer 2

for(int i=2;i<n;i++){
if(n%i==0){

  return false;

}
}
return true;