此题的意思是分解大数字，数字的范围是Longlong级别的，好像不能暴力的样子。但是，题目给出了个条件，最多只有一个因子的大小超过1000000。哈哈，这就是暴点啊。既然，如此直接枚举1000000以内的因子就行了，剩余的部分如果大于10的6次肯定是N的因子了，就不用暴力了。如果小于10的6次肯定是1啦，因为2-1000000的因子都被处理了啊。
这样这个题就不会超时了。确实，暴力是需要技巧的。还要注意uva上要用%lld输入。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #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;
}
|