轉(zhuǎn)載請(qǐng)注明出處：優(yōu)YoU http://user.qzone.qq.com/289065406/blog/1299063931
提示：100W真是大的BT。。。。我用了優(yōu)化還是勉強(qiáng)AC掉，認(rèn)識(shí)的一位達(dá)人，16ms AC這題，Orz....
解題思路：
如果還是按常規(guī)方法求
一百萬(wàn)內(nèi)
的所有素?cái)?shù)
(
就是除法求模
)
，時(shí)間復(fù)雜度是大到難以置信的。因此必須轉(zhuǎn)換思路進(jìn)行優(yōu)化，用加法代替除法，
用空間換取時(shí)間！
計(jì)算算加法絕對(duì)要比除法快得多，而且一百萬(wàn)個(gè)地址，也就是差不多
1MB
的內(nèi)存，相信現(xiàn)在
99%
的電腦還是可以很輕松地拿出來(lái)的！
判斷素?cái)?shù)的優(yōu)化：
1、
素?cái)?shù)除
2
外都是偶數(shù)，先減半
2、
遞歸法：如果一個(gè)數(shù)不能被比它小的所有素?cái)?shù)整除，那么它就是素?cái)?shù)。
3、
根號(hào)法：如果一個(gè)數(shù)
X
不能被
[2,
組合上面三個(gè)方法，可以大大減少時(shí)間復(fù)雜度，其實(shí)第
3
點(diǎn)是最有效的省時(shí)方法，能夠少做很多除法。
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
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
