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 次浏览

开启你的 职业生涯

完成课程以获得认证

开始学习
广告