麻煩了

以下是程式碼OTZ 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int main(void)
{
    long long int i,N,count=0; 
    scanf("%I64d",&N) ;
    count=0;

    for(i=1 ; i<=sqrt(N) ; i++)
    {
        if(N%i==0 && i!=sqrt(N))
        {
                    count+=2;
            printf("%I64d %I64d ",i,N/i);

        }
        else if(N%i==0 && i==sqrt(N))
        {
            printf("%I64d ",i);
            count++;
        }
        }
    if(N<=1)printf("非質數");
    else if(count==2)printf("質數\n");
    else{
         printf("非質數\n");
         } 
     

    return 0;
   

}

 判斷質數大家一定會想到最基本的作法：從 1 除到 n ， 只有 1 跟 n 整除的話就是質數

 但是這樣 2 的倍數都多檢查了

 接下來

 每個數的因數都是成雙成對出現

 除了完全平方數 ex: 4 = 1 * 4 = 2 * 2 還有 36 = 1 * 36 = 2 * 18 = 3 * 12 = 4 * 9 = 6 * 6

 從這裡可以發現過了 根號n 以後

 可以整除的數都可以在小於 根號n 的部分找到一個數字相乘並等於 n

 所以檢查大於 根號n 的部分是浪費時間 ( 很多人 TLE 的原因 !! )

 那麼經過上面兩點

 我們在檢查某數 n 的時候

 要先看看 n 是不是 2 的倍數

 再從 2 開始檢查到 根號 n 

 如果都沒有數可以整除 n

 那麼 n 就是質數

 以上就是這題要考的觀念

 當然還有更快的做法

 那就請大家自己再去研究吧