නිව්මන්-ෂෑන්ක්ස්-විලියම්ස් ප්‍රයිම්


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ හැකර් රැන්ක්
ගතික වැඩසටහන්කරණය ගණිතය ප්‍රධාන අංකය අනුපිළිවෙල

ගැටළු ප්රකාශය

නිව්මන්-ෂෑන්ක්ස්-විලියම්ස් ප්‍රයිම් (එන්එස්ඩබ්ලිව් ප්‍රයිම්) යනු පහත දැක්වෙන සූත්‍රය අනුව නිශ්චිත ස්වරූපයෙන් නිරූපණය කළ හැකි ප්‍රාථමික සංඛ්‍යාවක් මිස අන් කිසිවක් නොවේ:

එබැවින් අපි එන්එස්ඩබ්ලිව් ප්‍රයිම් සොයා ගත යුතුයි.

උදාහරණයක්

n = 3
7

පැහැදිලි කිරීම

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

ප්රවේශය

එන්එස්ඩබ්ලිව් ප්‍රාථමිකයන් මුලින්ම විස්තර කළේ මොරිස් නිව්මන්, ඩැනියෙල් ෂෑන්ක්ස් සහ හියු සී. විලියම්ස් විසිනි. 1981 දී වර්ග අනුපිළිවෙලක් සහිත සීමිත සරල කණ්ඩායම් අධ්‍යයනය කිරීමේදී.

පළමු NSW ප්‍රාථමිකයන් වන්නේ 7, 41, 239, 9369319, 63018038201,… (OEIS හි A088165 අනුක්‍රමය), 3, 5, 7, 19, 29,… (OEIS හි අනුක්‍රමය A005850) දර්ශකවලට අනුරූප වේ. Wikipedia විකිපීඩියාවෙන් ලබා ගත්}

ගැටලුවේදී, අපට ලබා දී ඇත්තේ n අංකයක් පමණි, එයින් ඇඟවෙන්නේ අපට n වන NSW ප්‍රයිම් සොයා ගත යුතු බවයි. පුනරාවර්තන සම්බන්ධතාවය භාවිතා කරමින් අපට NSW ප්‍රයිම් සොයාගත හැකිය.

පුනරාවර්තන සම්බන්ධතාවය

නිව්මන්-ෂෑන්ක්ස්-විලියම්ස් ප්‍රයිම්

එබැවින් යමෙකුට එන්එස්ඩබ්ලිව් ප්‍රයිම් සොයා ගැනීමට බොළඳ ප්‍රවේශයක් භාවිතා කළ හැකිය. බොළඳ ප්‍රවේශය සඳහා අපට පෙනෙන පරිදි සෑම එන්එස්ඩබ්ලිව් ප්‍රයිමයක් අවසාන එන්එස්ඩබ්ලිව් ප්‍රයිම් මත රඳා පවතින අතර අන්තිම සිට අන්තිම එන්එස්ඩබ්ලිව් ප්‍රයිම් මත රඳා පවතී. එබැවින් අපට ප්‍රයෝජන ගත හැකිය ගතික වැඩසටහන්කරණය, අපට අවසාන එන්එස්ඩබ්ලිව් ප්‍රාථමික දෙක ගබඩා කළ හැකිය. හේතුව අපි අවසාන එන්එස්ඩබ්ලිව් ප්‍රයිම් දෙක ඉතිරි නොකරන්නේ නම්. අපි ගැටළුව පුනරාවර්තන ආකාරයකින් විසඳනු ඇති අතර එමඟින් on ාතීය කාල සංකීර්ණත්වයක් ඇති වේ. මේ අනුව වර්තමාන on ාතීය කාල සංකීර්ණතාව රේඛීය කාල සංකීර්ණතාවයට අඩු කිරීම. අපි මෙම අගයන් මතක තබා ගන්නෙමු.

කේතය

නිව්මන්-ෂෑන්ක්ස්-විලියම්ස් ප්‍රයිම් සොයා ගැනීම සඳහා සී ++ කේතය

#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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

මත), අපි නව වන එන්එස්ඩබ්ලිව් ප්‍රයිම් සොයා ගන්නා තෙක් ලූප කළ යුතුය. කාල සංකීර්ණතාව රේඛීය වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1), ප්‍රති result ලය ගණනය කිරීම සඳහා අප භාවිතා කළ විචල්‍යයන් කුමක් වුවත් ආදානය මත රඳා නොපවතී. මේ අනුව අවකාශයේ සංකීර්ණතාව නියත ය.