ਨਿmanਮਨ – ਸ਼ੈਂਕਸ – ਵਿਲੀਅਮਜ਼ ਪ੍ਰਾਈਮ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਹੈਕਰਰੈਂਕ
ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ ਗਣਿਤ ਪ੍ਰਮੁਖ ਸੰਖਿਆ ਕ੍ਰਮ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਇਕ ਨਿmanਮਨ – ਸ਼ੈਂਕਸ – ਵਿਲੀਅਮਜ਼ ਪ੍ਰਾਈਮ (ਐਨਐਸਡਬਲਯੂ ਪ੍ਰਾਈਮ) ਇਕ ਪ੍ਰਮੁੱਖ ਨੰਬਰ ਤੋਂ ਇਲਾਵਾ ਕੁਝ ਵੀ ਨਹੀਂ ਹੈ ਜਿਸ ਨੂੰ ਹੇਠ ਦਿੱਤੇ ਫਾਰਮੂਲੇ ਦੇ ਅਨੁਸਾਰ ਇਕ ਵਿਸ਼ੇਸ਼ ਰੂਪ ਵਿਚ ਦਰਸਾਇਆ ਜਾ ਸਕਦਾ ਹੈ:

ਇਸ ਲਈ ਸਾਨੂੰ ਨੌਵਾਂ ਐਨਐਸਡਬਲਯੂ ਪ੍ਰਾਈਮ ਨੂੰ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ.

ਉਦਾਹਰਨ

n = 3
7

ਕਥਾ

S0 = 1, S1 = 1, S2 = 2 * S1 + S0 = 2 + 1 = 3, S3 = 2 * S2 + S1 = 2 * 3 + 1 = 7

ਪਹੁੰਚ

ਐਨਐਸਡਬਲਯੂ ਦੇ ਪ੍ਰਮੁੱਖਾਂ ਦਾ ਵੇਰਵਾ ਸਭ ਤੋਂ ਪਹਿਲਾਂ 1981 ਵਿੱਚ ਮੌਰਿਸ ਨਿmanਮਨ, ਡੈਨੀਅਲ ਸ਼ੈਂਕਸ ਅਤੇ ਹਿghਜ ਸੀ. ਵਿਲੀਅਮਜ਼ ਦੁਆਰਾ ਵਰਗ ਆਰਡਰ ਵਾਲੇ ਸੀਮਤ ਸਰਲ ਸਮੂਹਾਂ ਦੇ ਅਧਿਐਨ ਦੌਰਾਨ ਕੀਤਾ ਗਿਆ ਸੀ.

ਪਹਿਲੇ ਕੁਝ ਐਨਐਸਡਬਲਯੂ ਪ੍ਰਾਈਮ ਹਨ 7, 41, 239, 9369319, 63018038201,… (ਓਈਐਸ ਵਿੱਚ ਲੜੀ ਏ 088165), ਸੂਚਕਾਂਕ 3, 5, 7, 19, 29, (ਓਈਆਈਐਸ ਵਿੱਚ ਕ੍ਰਮ A005850) ਦੇ ਅਨੁਸਾਰ ਹਨ. Wikipedia ਵਿਕੀਪੀਡੀਆ ਤੋਂ ਲਿਆ}

ਸਮੱਸਿਆ ਵਿੱਚ, ਸਾਨੂੰ ਸਿਰਫ ਇੱਕ ਨੰਬਰ ਦਿੱਤਾ ਗਿਆ ਹੈ ਜੋ ਇਹ ਦਰਸਾਉਂਦਾ ਹੈ ਕਿ ਸਾਨੂੰ ਨੌਵੀਂ ਐਨਐਸਡਬਲਯੂ ਨੂੰ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਅਸੀਂ ਦੁਬਾਰਾ ਸੰਬੰਧਾਂ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹੋਏ NSW ਪ੍ਰਾਈਮ ਨੂੰ ਲੱਭ ਸਕਦੇ ਹਾਂ.

ਆਵਰਤੀ ਸੰਬੰਧ

ਨਿmanਮਨ – ਸ਼ੈਂਕਸ – ਵਿਲੀਅਮਜ਼ ਪ੍ਰਾਈਮ

ਇਸ ਲਈ ਕੋਈ ਵੀ ਨੌਵੀਂ ਐਨਐਸਡਬਲਯੂ ਪ੍ਰਾਈਮ ਨੂੰ ਲੱਭਣ ਲਈ ਇੱਕ ਭੋਲੇਪਣ ਦੀ ਵਰਤੋਂ ਕਰ ਸਕਦਾ ਹੈ. ਭੋਲੇ ਪਹੁੰਚ ਲਈ ਜਿਵੇਂ ਅਸੀਂ ਵੇਖ ਸਕਦੇ ਹਾਂ ਕਿ ਹਰੇਕ ਐਨਐਸਡਬਲਯੂ ਪ੍ਰਾਈਮ ਆਖਰੀ ਐਨਐਸਡਬਲਯੂ ਪ੍ਰਾਈਮ ਅਤੇ ਆਖਰੀ ਤੋਂ ਆਖਰੀ ਐਨਐਸਡਬਲਯੂ ਪ੍ਰਾਈਮ ਤੇ ਨਿਰਭਰ ਕਰਦਾ ਹੈ. ਇਸ ਲਈ ਅਸੀਂ ਇਸ ਦੀ ਵਰਤੋਂ ਕਰ ਸਕਦੇ ਹਾਂ ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ, ਜਿੱਥੇ ਅਸੀਂ ਪਿਛਲੇ ਦੋ ਐਨਐਸਡਬਲਯੂ ਪ੍ਰਾਈਮਸ ਨੂੰ ਸਟੋਰ ਕਰ ਸਕਦੇ ਹਾਂ. ਕਾਰਨ ਜੇ ਅਸੀਂ ਪਿਛਲੇ ਦੋ ਐਨਐਸਡਬਲਯੂ ਪ੍ਰਾਈਮ ਨੂੰ ਨਹੀਂ ਬਚਾਉਂਦੇ. ਅਸੀਂ ਸਮੱਸਿਆ ਨੂੰ ਇੱਕ ਆਵਰਤੀ ਫੈਸ਼ਨ ਵਿੱਚ ਹੱਲ ਕਰਾਂਗੇ ਜਿਸਦਾ ਨਤੀਜਾ ਘਾਤਕ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਦਾ ਹੋਵੇਗਾ. ਇਸ ਤਰ੍ਹਾਂ ਮੌਜੂਦਾ ਐਕਸਪੈਨਸ਼ਨਲ ਟਾਈਮ ਗੁੰਝਲਤਾ ਨੂੰ ਰੇਖਿਕ ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ ਨੂੰ ਘਟਾਉਣ ਲਈ. ਅਸੀਂ ਇਨ੍ਹਾਂ ਕਦਰਾਂ ਕੀਮਤਾਂ ਨੂੰ ਯਾਦ ਕਰਾਂਗੇ.

ਕੋਡ

ਸੀ ++ ਕੋਡ ਨੂੰ ਨੌਵਾਂ ਨਿmanਮਨ – ਸ਼ੈਂਕਸ – ਵਿਲੀਅਮਜ਼ ਪ੍ਰਾਈਮ ਲੱਭਣ ਲਈ

#include <bits/stdc++.h>
using namespace std;

int main(){
  // nth NSW prime which is wanted
  int n;cin>>n;

  if(n == 0 || n == 1)
    cout<<1;
  else{
    int lastToLast = 1, last = 1;
    int cur;
    for(int i=2;i<=n;i++){
      cur = 2*last + lastToLast;
      lastToLast = last;
      last = cur;
    }
    cout<<cur;
  }
}
4
17

ਨੌਵਾਂ ਨਿmanਮਨ – ਸ਼ੈਂਕਸ – ਵਿਲੀਅਮਜ਼ ਪ੍ਰਾਈਮ ਲੱਭਣ ਲਈ ਜਾਵਾ ਕੋਡ

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // nth NSW prime which is wanted
    int n = sc.nextInt();

    if(n == 0 || n == 1)
      System.out.print(1);
    else{
      int lastToLast = 1, last = 1;
      int cur = 0;
      for(int i=2;i<=n;i++){
        cur = 2*last + lastToLast;
        lastToLast = last;
        last = cur;
      }
      System.out.print(cur);
    }
    }
}
4
17

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਕਿਉਂਕਿ ਸਾਨੂੰ ਲੂਪ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਜਦੋਂ ਤਕ ਸਾਨੂੰ ਨੌਵਾਂ ਐਨਐਸਡਬਲਯੂ ਪ੍ਰਾਈਮ ਨਹੀਂ ਮਿਲਦਾ. ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ ਰੇਖਿਕ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (1), ਕਿਉਂਕਿ ਜੋ ਵੀ ਪਰਿਵਰਤਨ ਅਸੀਂ ਨਤੀਜਿਆਂ ਦੀ ਗਣਨਾ ਲਈ ਵਰਤੇ ਹਨ ਉਹ ਇਨਪੁਟ ਤੇ ਨਿਰਭਰ ਨਹੀਂ ਕਰਦੇ. ਇਸ ਤਰ੍ਹਾਂ ਪੁਲਾੜ ਦੀ ਜਟਿਲਤਾ ਨਿਰੰਤਰ ਹੈ.