C++質因數

【質因數】

問題描述：

非質數的正整數m可被分解成數個因數，而m可被其任何一個因數整除，例如：12的因數有6、4、3、2。但其中有些因數為質數稱為質因數。例如：12的質因數有3、2。

輸入說明：

程式的輸入包含n+1行數字，第一行包含一個正整數n，1 ≤ n ≤ 30，代表有n筆測試資料。第二行開始輸入n筆測試資料m，m ≤ 30000000000000。

輸出說明：

由小到大輸出n筆測試資料m的質因數，質因數之間以空格隔開，每一筆輸出最後有跳行，每一行最後面不能有空格，如果m不能因數分解則輸出1。

【輸入範例】	【輸出範例】
4 8 12 100000 19	2 2 3 2 5 1

1. 時間需大致控制在1秒內
2. 須考慮到大數運算

#include<iostream>
using namespace std;

int main()
{
int n,a,b;
long long m,c;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> m;
a = 0;
b = 0;
c = m;
for (long long j = 2;j * j <= c; j++)
{
a = 0;
if (j % 2 == 0 && j > 2)
continue;
if (c % j == 0)
{
while (c % j == 0)
{
c /= j;
a = 1;
}
}
if (a == 1)
{
if (b > 0)
cout << " ";
cout << j;
b++;
}
}
if (b == 0)
cout << 1;
else if (c > 1 && c != m)
{
if (b > 0)
cout << " ";
cout << c;
b++;
}
cout << endl;
}
return 0;
}