# Newman–Shanks–Williams prime

In mathematics, a Newman–Shanks–Williams prime (NSW prime) is a prime number p which can be written in the form: Recurrence relation for Newman–Shanks–Williams prime is:   The first few terms of the sequence are 1, 1, 3, 7, 17, 41, 99, ….

Examples:

```Input : n = 3
Output : 7

Input : n = 4
Output : 17
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Below is the implementation of finding nth Newman–Shanks–Williams prime:

## C++

 `// CPP Program to find Newman–Shanks–Williams prime ` `#include ` `using` `namespace` `std; ` ` `  `// return nth Newman–Shanks–Williams prime ` `int` `nswp(``int` `n) ` `{ ` `    ``// Base case ` `    ``if` `(n == 0 || n == 1) ` `        ``return` `1; ` ` `  `    ``// Recursive step ` `    ``return` `2 * nswp(n - 1) + nswp(n - 2); ` `} ` ` `  `// Driven Program ` `int` `main() ` `{ ` `    ``int` `n = 3; ` ` `  `    ``cout << nswp(n) << endl; ` `    ``return` `0; ` `} `

## Java

 `// Java Program to find  ` `// Newman-Shanks-Williams prime ` `class` `GFG ` `{ ` `// return nth Newman-Shanks-Williams ` `// prime ` `static` `int` `nswp(``int` `n) ` `{ ` `    ``// Base case ` `    ``if` `(n == ``0` `|| n == ``1``) ` `        ``return` `1``; ` ` `  `    ``// Recursive step ` `    ``return` `2` `* nswp(n - ``1``) + nswp(n - ``2``); ` `} ` ` `  `// Driver code  ` `public` `static` `void` `main (String[] args) ` `{ ` `    ``int` `n = ``3``; ` `    ``System.out.println(nswp(n)); ` `} ` `} ` ` `  `// This code is contributed by Anant Agarwal. `

## Python3

 `# Python3 Program to find Newman–Shanks–Williams prime ` ` `  `# return nth Newman–Shanks–Williams prime ` `def` `nswp(n): ` `     `  `    ``# Base case ` `    ``if` `n ``=``=` `0` `or` `n ``=``=` `1``: ` `        ``return` `1` ` `  `    ``# Recursive step ` `    ``return` `2` `*` `nswp(n ``-` `1``) ``+` `nswp(n ``-` `2``) ` ` `  `# Driven Program ` `n ``=` `3` `print` `(nswp(n)) ` ` `  ` `  `# This code is contributed by Shreyanshi Arun. `

## C#

 `// C# Program to find ` `// Newman-Shanks-Williams prime ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// return nth Newman-Shanks-Williams ` `    ``// prime ` `    ``static` `int` `nswp(``int` `n) ` `    ``{ ` `         `  `        ``// Base case ` `        ``if` `(n == 0 || n == 1) ` `            ``return` `1; ` ` `  `        ``// Recursive step ` `        ``return` `2 * nswp(n - 1) + nswp(n - 2); ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `n = 3; ` `         `  `        ``Console.WriteLine(nswp(n)); ` `    ``} ` `} ` ` `  `// This code is contributed by vt_m. `

## PHP

 ` `

Output:

```7
```

Below is Dynamic Programming solution of finding nth Newman–Shanks–Williams prime:

## C++

 `// CPP Program to find Newman–Shanks–Williams prime ` `#include ` `using` `namespace` `std; ` ` `  `// return nth Newman–Shanks–Williams prime ` `int` `nswp(``int` `n) ` `{ ` `    ``int` `dp[n + 1]; ` ` `  `    ``// Base case ` `    ``dp = dp = 1; ` ` `  `    ``// Finding nth Newman–Shanks–Williams prime ` `    ``for` `(``int` `i = 2; i <= n; i++) ` `        ``dp[i] = 2 * dp[i - 1] + dp[i - 2]; ` ` `  `    ``return` `dp[n]; ` `} ` ` `  `// Driver Program ` `int` `main() ` `{ ` `    ``int` `n = 3; ` ` `  `    ``cout << nswp(n) << endl; ` `    ``return` `0; ` `} `

## Java

 `// Java Program for finding ` `// Newman-Shanks-Williams prime ` `import` `java.util.*; ` ` `  `class` `GFG ` `{ ` `    ``// return nth Newman_Shanks_Williams prime ` `    ``public` `static` `int` `nswpn(``int` `n) ` `    ``{ ` `        ``int` `dp[] = ``new` `int``[n + ``1``]; ` `         `  `        ``// Base case ` `        ``dp[``0``] = dp[``1``] = ``1``; ` `         `  `        ``// Finding nth Newman_Shanks_Williams prime ` `        ``for` `(``int` `i = ``2``; i <= n; i++) ` `          ``dp[i] = ``2` `* dp[i - ``1``] + dp[i - ``2``]; ` `         `  `        ``return` `dp[n]; ` `    ``} ` `     `  `    ``// Driver Program ` `    ``public` `static` `void` `main (String[] args) { ` `         `  `        ``int` `n = ``3``; ` `         `  `        ``System.out.println(nswpn(n)); ` `    ``} ` `} ` ` `  `/* This code is contributed by Akash Singh */`

## Python3

 `# Python3 Program to find  ` `# Newman–Shanks–Williams prime ` ` `  `# return nth Newman–Shanks ` `# –Williams prime ` `def` `nswp(n): ` `     `  `    ``# Base case ` `    ``dp ``=` `[``1` `for` `x ``in` `range``(n ``+` `1``)]; ` `     `  `    ``# Finding nth Newman–Shanks ` `    ``# –Williams prime ` `    ``for` `i ``in` `range``(``2``, n ``+` `1``): ` `        ``dp[i] ``=` `(``2` `*` `dp[i ``-` `1``] ``+`  `                     ``dp[i ``-` `2``]); ` `    ``return` `dp[n]; ` ` `  `# Driver Code ` `n ``=` `3``; ` `print``(nswp(n)); ` ` `  `# This code is contributed ` `# by mits `

## C#

 `// C# Program to find Newman–Shanks–Williams prime ` ` `  `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// return nth Newman–Shanks–Williams prime ` `    ``static` `int` `nswp(``int` `n) ` `    ``{ ` `         `  `        ``int``[] dp = ``new` `int``[n + 1]; ` ` `  `        ``// Base case ` `        ``dp = dp = 1; ` ` `  `        ``// Finding nth Newman–Shanks–Williams prime ` `        ``for` `(``int` `i = 2; i <= n; i++) ` `            ``dp[i] = 2 * dp[i - 1] + dp[i - 2]; ` ` `  `        ``return` `dp[n]; ` `    ``} ` ` `  `    ``// Driver Program ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `n = 3; ` ` `  `        ``Console.WriteLine(nswp(n)); ` `    ``} ` `} ` ` `  `// This code is contributed by vt_m. `

## PHP

 ` `

Output:

```7
```