转载请注明出处:優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 }