轉載請注明出處：優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
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
