POJ2262-Goldbach's Conjecture

系统 1853 0

转载请注明出处:優YoU http://user.qzone.qq.com/289065406/blog/1299063931

提示:100W真是大的BT。。。。我用了优化还是勉强AC掉,认识的一位达人,16ms AC这题,Orz....

解题思路:

 

如果还是按常规方法求 一百万内 的所有素数 ( 就是除法求模 ) ,时间复杂度是大到难以置信的。因此必须转换思路进行优化,用加法代替除法, 用空间换取时间! 计算算加法绝对要比除法快得多,而且一百万个地址,也就是差不多 1MB 的内存,相信现在 99% 的电脑还是可以很轻松地拿出来的!

 

判断素数的优化:

1、 素数除 2 外都是偶数,先减半

2、 递归法:如果一个数不能被比它小的所有素数整除,那么它就是素数。

3、 根号法:如果一个数 X 不能被 [2,  根号X ] 内的所有数整除,那么它就是素数

 

组合上面三个方法,可以大大减少时间复杂度,其实第 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 }

POJ2262-Goldbach's Conjecture


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧,狠狠点击下面给点支持吧,站长非常感激您!手机微信长按不能支付解决办法:请将微信支付二维码保存到相册,切换到微信,然后点击微信右上角扫一扫功能,选择支付二维码完成支付。

【本文对您有帮助就好】

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧,站长会非常 感谢您的哦!!!

发表我的评论
最新评论 总共0条评论