C++ 中的 Newman-Shanks-Williams 素數

newman-shanks-williams 素數序列如下所示

1, 1, 3, 7, 17, 41...

如果我們對序列中的項進行推廣，則得到

a0=1
a1=1
an=2*a(n-1)+a(n-2)

演算法

  • 初始化數字 n。
  • 初始化序列開頭數字為 1 和 1。
  • 編寫一個迴圈，迭代至 n。
    • 使用前一個數字計算下一個數字。
    • 更新前兩個數字。
  • 返回最後一個數字。

實現

以下是上述演算法在 C++ 中的實現

#include <bits/stdc++.h>
using namespace std;
int getNthTerm(int n) {
   if(n == 0 || n == 1) {
      return 1;
   }
   int a = 1, b = 1;
   for(int i = 3; i <= n; ++i) {
      int c = 2 * b + a;
      a = b;
      b = c;
   }
   return b;
}
int main() {
   int n = 5;
   cout << getNthTerm(n) << endl;
   return 0;
}

輸出

如果你執行以上程式碼，則會得到以下結果。

17

更新於： 2021 年 10 月 23 日

93 次瀏覽

開啟你的 職業生涯

完成課程以獲得認證

開始學習
廣告