亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

POJ2262-Goldbach's Conjecture

系統(tǒng) 2047 0

轉(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, ?根號(hào)X ] 內(nèi)的所有數(shù)整除,那么它就是素?cái)?shù)

?

組合上面三個(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 }

POJ2262-Goldbach's Conjecture


更多文章、技術(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ì)您有幫助就好】

您的支持是博主寫(xiě)作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長(zhǎng)會(huì)非常 感謝您的哦!!!

發(fā)表我的評(píng)論
最新評(píng)論 總共0條評(píng)論
主站蜘蛛池模板: 黄色高清在线观看 | 国产主播第一页 | 久久国产精品偷 | 亚洲综合国产一区在线 | 日本a毛片在线播放 | 久久99精品久久久久久国产越南 | 欧美亚洲国产精品久久高清 | 新香蕉视频在线 | 天天骑天天干 | 日本免费不卡 | 高清欧美一区二区免费影视 | 中文字幕一二三区乱码老 | 亚洲精品久久 | 五月婷婷在线免费观看 | 国产伦久视频免费观看 视频 | 一区二区三区在线播放视频 | 国产精品久久久久久久久久久威 | 色综合久久久久久久 | 美女在线看永久免费网址 | 亚洲精品免费视频 | 午夜一级毛片看看 | 老司机午夜免费影院 | 一本久草 | 国产成人久久精品一区二区三区 | 亚洲sss综合天堂久久久 | 97人人插 | 大杳焦伊人久久综合热 | 亚洲国产成人91精品 | 成年人一级黄色片 | 国产精品手机在线观看 | 欧美 亚洲 另类 热图 | 国产精欧美一区二区三区 | 中文字幕一区二区三区四区五区人 | 6080欧美一区二区三区四区 | 亚洲国产成人久久一区二区三区 | 99热久久国产精品免费看 | 2018天天操天天干 | 毛片视 | 国产福利在线免费观看 | 日韩精品国产自在欧美 | 中文字幕在线免费视频 |