高中生程式解題系統 a007: 判斷質數

這題真的非常的怪異="= 應該說我寫的程式逾時了Orz

第一版

#include "iostream"
using namespace std; 
int main()
{
    int intA,intB,intC;
    while (cin >> intA){
    int boolA = 1;
    for(intB=2;intB<(intA>>1);intB++){
        for(intC=1;intC<(intA>>1);intC++){
            if(intA %(intB*intC)==0)
                boolA= 0;
                break;
        }
    }
    if(boolA==1)
        cout << "質數" << endl;
    else
        cout << "非質數" << endl;
    }
    return 0;
}

這版逾時超過兩秒

第二版

#include "iostream"
#include "cmath"
using namespace std; 
int main()
{
    int intA,intB,intC;
    while (cin >> intA){
        int boolA = 1;
        intC = (int)(sqrt((double)intA));
        for(int i = 2; i<=intC;i++) {
            if(intA % i == 0) {
                boolA = 0;
                break;
        }
    }
    if(boolA==1)
        cout << "質數" << endl;
    else
        cout << "非質數" << endl;
    }
    return 0;
}

這版也逾時了Q_Q

討論區有人用 Sieve of Eratosthenes miller-Rabin 來寫 (不是基礎題嗎Q_Q 怎麼要用演算法...)，另外就是使用列表法把 sqrt(2147483647) 拿來判斷...，只能說這題算是目前我碰到的問題最困難的一個!!