我的想法是：使用者輸入一個數 ( x ) 之後，用 for 迴圈讓 x 除以 i ( i 從 2 開始，i 等於 x-1 時為最後一項 )，只要 2 到 x-1 之間任一個數除出來的餘數為 0，就把因數 ( factor ) 的數量 +1。

之後再判斷 factor 的數值，如果 factor 為 0 ( 即 2 ~ x-1 之間沒有任何數能整除 x )，就判斷 x 為質數。

不過卻一直出現執行逾時，看了討論之後發現使用sqrt可以解決逾時的問題。

不過難道除了sqrt就沒有其他的方法了嗎？

 

無sqrt程式碼：

#include <iostream>

using namespace std;

int x,factor;


int main() {
  while ( cin >> x )
  {
    for ( int i=2; i<x; i++ )
        {
            if ( x%i == 0 )
            { factor++; }
        }
            if ( factor == 0 )
              { cout << "質數" << endl; factor = 0; }
            else
              { cout << "非質數" << endl; factor = 0; }
  }
    return 0;
}