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