转载请注明出处：優YoU http://user.qzone.qq.com/289065406/blog/1299063931
提示：100W真是大的BT。。。。我用了优化还是勉强AC掉，认识的一位达人，16ms AC这题，Orz....
解题思路：
如果还是按常规方法求
一百万内
的所有素数
(
就是除法求模
)
，时间复杂度是大到难以置信的。因此必须转换思路进行优化，用加法代替除法，
用空间换取时间！
计算算加法绝对要比除法快得多，而且一百万个地址，也就是差不多
1MB
的内存，相信现在
99%
的电脑还是可以很轻松地拿出来的！
判断素数的优化：
1、
素数除
2
外都是偶数，先减半
2、
递归法：如果一个数不能被比它小的所有素数整除，那么它就是素数。
3、
根号法：如果一个数
X
不能被
[2,
组合上面三个方法，可以大大减少时间复杂度，其实第
3
点是最有效的省时方法，能够少做很多除法。
1
//
Memory Time
2
//
228K 907MS
3
#include
<
iostream
>
4
using
namespace
std;
5
6
bool
judge_prime(
int
digit)
7
{
8
9
int
i,flag;
10
if
(digit
%
2
==
0
)
11
return
false
;
12
else
13
{
14
for
(i
=
3
,flag
=
1
;i
*
i
<=
digit;i
+=
2
)
15
if
(digit
%
i
==
0
)
16
{
17
flag
=
0
;
18
break
;
19
}
20
if
(flag)
21
return
true
;
22
}
23
return
false
;
24
}
25
26
int
main(
void
)
27
{
28
int
temp,num,flag;
29
for
(;;)
30
{
31
cin
>>
num;
32
if
(num
%
2
!=
0
||
num
<
6
)
33
return
0
;
34
for
(temp
=
3
,flag
=
1
;temp
<=
num
/
2
;temp
+=
2
)
35
if
(judge_prime(temp)
&&
judge_prime(num
-
temp))
36
{
37
cout
<<
num
<<
"
=
"
<<
temp
<<
"
+
"
<<
num
-
temp
<<
endl;
38
flag
=
0
;
39
break
;
40
}
41
if
(flag)
42
cout
<<
"
Goldbach's conjecture is wrong.
"
<<
endl;
43
44
}
45
return
0
;
46
}
