好奇怪= =這題這麼難都沒有人問...

我用了好幾種方法...

但是全部都沒過= =""...

我的程式碼:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int q=0;
    while(scanf("%d",&q),q){                    //q為輸入的數
        printf("%d : ",q);                      //先輸出前半段
        int k=0;                                //k為答案(後半段)
        if(q%2==0){                             //先判斷唯一偶數的質數
            q/=2;
            k++;
            while(q%2==0){
                q/=2;
            }
        }
        for(int j=3;j<=q;j+=2){                 //j為質數(未判斷的)
            if(j>sqrtf(q)&&k==0){               //判斷輸入的q是否為質數
                k++;
                break;
            }
            int g=1;                            //g=1的話j就是質數
            if(j>8){
                for(int i=3;i<=sqrtf(j);i+=2){  //用i判斷j是否為質數
                    if(j%i==0){
                        g=0;
                        break;
                    }
                }
            }
            if(g==1&&q%j==0){
                q/=j;
                k++;
                while(g==1&&q%j==0){
                    q/=j;
                }
            }
        }
        printf("%d\n",k);
    }
    return 0;
}

這一題只有用6ms是怎麼算的阿?

是一開始就做好質數表嗎?

因為我都已經用Sieve of Eratosthenes做了.... ><

(6ms) 

我只有建出1000以內的質數來判斷，如果無法整除到最後為1 那麼我必定知道它為一個質數 輸出它