探索合數世紀題解

  • 2020 年 5 月 30 日
  • 筆記

探索合數世紀

問題描述

　　若一個世紀的100年號中不存在一個素數，則稱這個世紀為合數世紀。求第n個合數世紀（公元0年起始）。

輸入描述

　　輸入n，為整數

輸出描述

　　輸出合數世紀起始與結束年份，用空格隔開

樣例輸入

1

樣例輸出

1671800 1671899

 

　　這道題是一道遍歷題，遍歷0-99，沒有合數世紀就累加100，訣竅在於如何讓代碼的效率更好。

　　我首先想到的是，用for循環對0到99進行素數判斷，只要有一個素數就認為這個世紀不行，判斷素數我用的代碼如下

1 int judge(int n)
2 {
3     int sum=0;
4     for(int i=2;i<n/2;i++)
5     {
6         if(num%i==0)    return 0;
7     }
8     return 1;
9 }

　　於是問題出現了，判斷素數的代碼上面這個已經是我能想到的效率最快的一個了，但還是不行，時間複雜度約為為O(n/2)，隨着n越大，循環次數越多，時間用得也越多，也就導致了，第一個合數世紀超過三秒還是判斷不出來，我們以1秒的標準要求自己。

　　查了一下資料，我發現了一個時間複雜度更低的算法。

　　我原先是打算判斷是不是素數，而我現在我打算判斷是不是合數，代碼如下

1 int judge(int n)
2 {
3     int sum=0;
4     for(int i=2;i*i<=n;i++)
5     {
6         if(n%i==0)  return 1;
7     }
8     return 0;
9 }

　　很巧妙的一個判斷是否是合數，時間複雜度為最大為O(n^0.5)，遠遠小於O(n/2)。

　　於是，我用這個算法打造了一個程序，如下

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int judgecompos(int n)    //在n~n+99之內進行素數累加
 5 {
 6     int count=0;
 7     for(int i=n+1;i<n+100;i+=2)    //省去偶數，節約時間
 8     {
 9         for(int j=2;j*j<=i;j++)
10         {
11             if(i%j==0)
12             {
13                 count++;    //素數累加
14                 break;
15             }
16         }
17     }
18     if(count==50)   return 1;
19     else    return 0;
20 }
21 
22 int main()
23 {
24     int begin=0,n=0;
25     cin>>n;
26     for(int i=1671700;;i+=100)    //這裡取了一個巧，i從1671700開始，i從0開始也是沒問題的
27     {
28         if(judgecompos(i)==1)
29         {
30             begin++;
31         }
32         if(n==begin)
33         {
34             cout<<i<<' '<<i++99<<endl;
35         　　 break;
36         }
37     }
38     return 0;
39 }

　　相比於原來的素數判斷來說，這的是節省了很多時間，如果你有更好的代碼和思路，歡迎交流！

 

VirMach 便宜 VPS

QNews

QNews