此題的意思是分解大數(shù)字，數(shù)字的范圍是Longlong級(jí)別的，好像不能暴力的樣子。但是，題目給出了個(gè)條件，最多只有一個(gè)因
子的大小超過(guò)1000000。哈哈，這就是暴點(diǎn)啊。既然，如此直接枚舉1000000以內(nèi)的因子就行了，剩余的部分如果大于10的6次
肯定是N的因子了，就不用暴力了。如果小于10的6次肯定是1啦，因?yàn)?-1000000的因子都被處理了啊。
這樣這個(gè)題就不會(huì)超時(shí)了。確實(shí)，暴力是需要技巧的。還要注意uva上要用%lld輸入。
#include <stdio.h>
#include <math.h>
typedef long long LL;
#define MAX (6000000)
bool bPrime[MAX];
int nPrime[MAX];
int nNum;
void InitPrime()
{
LL nMax = sqrt(MAX) + 1;
bPrime[0] = bPrime[1] = true;
for (int i = 2; i <= nMax; ++i)
{
if (!bPrime[i])
{
for (int j = 2 * i; j < MAX; j += i)
{
bPrime[j] = true;
}
}
}
for (int i = 2; i < MAX; ++i)
{
if (!bPrime[i])
nPrime[nNum++] = i;
}
}
bool IsPrime(LL nN)
{
if (nN < MAX) return !bPrime[nN];
LL nMax = sqrt((double)nN) + 1;
for (LL j = 0, i = nPrime[j]; i <= nMax; ++j, i = nPrime[j])
{
if (nN % i == 0)
{
return false;
}
}
return true;
}
int main()
{
LL nN;
InitPrime();
while (scanf("%lld", &nN), nN >= 0)
{
if (nN <= 2)
{
printf("%-lld\n\n", nN);
continue;
}
int nMax = sqrt((double)nN)+ 1;
for (LL i = 2; i <= 1000000 && i <= nMax; ++i)
{
while (nN % i == 0)
{
printf(" %-lld\n", i);
nN /= i;
}
if (nN < 6000000 && IsPrime(nN))
{
break;
}
}
if (nN != 1)
printf(" %-lld\n", nN);
printf("\n");
}
return 0;
}