ന്യൂമാൻ-ഷാങ്ക്സ്-വില്യംസ് പ്രൈം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ഹാക്കർ റാങ്ക്
ഡൈനാമിക് പ്രോഗ്രാമിംഗ് മഠം പ്രൈം നമ്പർ അനുക്രമം

പ്രശ്നം പ്രസ്താവന

ഒരു ന്യൂമാൻ-ഷാങ്ക്സ്-വില്യംസ് പ്രൈം (എൻ‌എസ്‌ഡബ്ല്യു പ്രൈം) എന്നത് ഒരു പ്രൈം നമ്പറല്ലാതെ മറ്റൊന്നുമല്ല, അത് ഇനിപ്പറയുന്ന സൂത്രവാക്യം അനുസരിച്ച് ഒരു നിർദ്ദിഷ്ട രൂപത്തിൽ പ്രതിനിധീകരിക്കാം:

അതിനാൽ നമ്മൾ എൻ‌എസ്‌ഡബ്ല്യു പ്രൈം കണ്ടെത്തേണ്ടതുണ്ട്.

ഉദാഹരണം

n = 3
7

വിശദീകരണം

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

സമീപനം

ചതുരാകൃതിയിലുള്ള പരിമിത ലളിതമായ ഗ്രൂപ്പുകളെക്കുറിച്ചുള്ള പഠനത്തിനിടെ 1981 ൽ മോറിസ് ന്യൂമാൻ, ഡാനിയൽ ഷാങ്ക്സ്, ഹഗ് സി. വില്യംസ് എന്നിവർ എൻ‌എസ്‌ഡബ്ല്യു പ്രൈമുകളെ ആദ്യമായി വിവരിച്ചു.

ആദ്യത്തെ കുറച്ച് എൻ‌എസ്‌ഡബ്ല്യു പ്രൈമുകൾ 7, 41, 239, 9369319, 63018038201,… (ഒ‌ഇ‌ഐ‌എസിലെ A088165 സീക്വൻസ്), 3, 5, 7, 19, 29,… Wikipedia വിക്കിപീഡിയയിൽ നിന്ന് എടുത്തത്}

പ്രശ്‌നത്തിൽ‌, നമുക്ക് എൻ‌എസ്‌ഡബ്ല്യു പ്രൈം കണ്ടെത്തേണ്ടതുണ്ടെന്ന് സൂചിപ്പിക്കുന്ന ഒരു നമ്പർ n മാത്രമേ നൽകിയിട്ടുള്ളൂ. ആവർത്തന ബന്ധം ഉപയോഗിച്ച് നമുക്ക് എൻ‌എസ്‌ഡബ്ല്യു പ്രൈം കണ്ടെത്താനാകും.

ആവർത്തന ബന്ധം

ന്യൂമാൻ-ഷാങ്ക്സ്-വില്യംസ് പ്രൈം

അതിനാൽ ഒരാൾക്ക് എൻ‌എസ്‌ഡബ്ല്യു പ്രൈം കണ്ടെത്തുന്നതിന് നിഷ്കളങ്കമായ ഒരു സമീപനം ഉപയോഗിക്കാം. നിഷ്കളങ്കമായ സമീപനത്തിനായി, ഓരോ എൻ‌എസ്‌ഡബ്ല്യു പ്രൈമും അവസാന എൻ‌എസ്‌ഡബ്ല്യു പ്രൈമിനെ ആശ്രയിച്ചിരിക്കുന്നുവെന്നും അവസാനത്തേത് മുതൽ എൻ‌എസ്‌ഡബ്ല്യു പ്രൈം വരെ ആശ്രയിച്ചിരിക്കുന്നുവെന്നും നമുക്ക് കാണാൻ കഴിയും. അതിനാൽ നമുക്ക് ഉപയോഗപ്പെടുത്താം ഡൈനാമിക് പ്രോഗ്രാമിംഗ്, അവസാന രണ്ട് എൻ‌എസ്‌ഡബ്ല്യു പ്രൈമുകൾ‌ സംഭരിക്കാൻ‌ ഇവിടെ. അവസാന രണ്ട് എൻ‌എസ്‌ഡബ്ല്യു പ്രൈമുകൾ‌ ഞങ്ങൾ‌ സംരക്ഷിച്ചില്ലെങ്കിൽ‌ കാരണം. എക്‌സ്‌പോണൻഷ്യൽ സമയ സങ്കീർണ്ണതയ്ക്ക് കാരണമാകുന്ന ഒരു ആവർത്തന രീതിയിൽ ഞങ്ങൾ പ്രശ്‌നം പരിഹരിക്കും. നിലവിലെ എക്‌സ്‌പോണൻഷ്യൽ സമയ സങ്കീർണ്ണതയെ ലീനിയർ സമയ സങ്കീർണ്ണതയിലേക്ക് കുറയ്ക്കുന്നതിന്. ഈ മൂല്യങ്ങൾ ഞങ്ങൾ ഓർമ്മിക്കും.

കോഡ്

ന്യൂമാൻ-ഷാങ്ക്സ്-വില്യംസ് പ്രൈം കണ്ടെത്തുന്നതിനുള്ള സി ++ കോഡ്

#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

ന്യൂമാൻ-ഷാങ്ക്സ്-വില്യംസ് പ്രൈം കണ്ടെത്തുന്നതിനുള്ള ജാവ കോഡ്

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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), nth NSW പ്രൈം കണ്ടെത്തുന്നതുവരെ ഞങ്ങൾ ലൂപ്പ് ചെയ്യേണ്ടതുണ്ട്. സമയ സങ്കീർണ്ണത രേഖീയമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1)കാരണം, ഫലം കണക്കുകൂട്ടാൻ ഞങ്ങൾ ഉപയോഗിച്ച വേരിയബിളുകൾ എന്തായാലും ഇൻപുട്ടിനെ ആശ്രയിക്കുന്നില്ല. അങ്ങനെ സ്ഥല സങ്കീർണ്ണത സ്ഥിരമാണ്.