Newman – Shanks – Williams ນາຍົກລັດຖະ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ແຮກເກີຣ
ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ຄະນິດສາດ ຈຳ ນວນ Prime ລໍາດັບ

ຖະແຫຼງການບັນຫາ

A Newman-Shanks – Williams prime (NSW prime) ແມ່ນບໍ່ມີຫຍັງນອກ ເໜືອ ຈາກຕົວເລກທີ່ ສຳ ຄັນທີ່ສາມາດເປັນຕົວແທນໃນຮູບແບບສະເພາະໃດ ໜຶ່ງ ທີ່ມີໃນສູດດັ່ງຕໍ່ໄປນີ້:

ດັ່ງນັ້ນພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາ NSW ທີ່ ສຳ ຄັນ.

ຍົກຕົວຢ່າງ

n = 3
7

ຄໍາອະທິບາຍ

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

ວິທີການ

NSW primes ໄດ້ຖືກອະທິບາຍເປັນຄັ້ງ ທຳ ອິດໂດຍ Morris Newman, Daniel Shanks ແລະ Hugh C. Williams ໃນປີ 1981 ໃນໄລຍະການສຶກສາກຸ່ມງ່າຍໆທີ່ມີລະບຽບຮຽບຮ້ອຍ.

ສອງສາມ NSW ຄັ້ງ ທຳ ອິດແມ່ນ 7, 41, 239, 9369319, 63018038201, … (ລຳ ດັບ A088165 ໃນ OEIS), ກົງກັບຕົວຊີ້ວັດ 3, 5, 7, 19, 29, … (ລຳ ດັບ A005850 ໃນ OEIS). {ເອົາມາຈາກ Wikipedia}

ໃນບັນຫາ, ພວກເຮົາໄດ້ຮັບພຽງແຕ່ ໝາຍ ເລກ n ເຊິ່ງ ໝາຍ ຄວາມວ່າພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາ NSW ທີ່ ສຳ ຄັນ. ພວກເຮົາສາມາດຊອກຫານາຍົກລັດຖະມົນຕີ NSW ໂດຍ ນຳ ໃຊ້ຄວາມ ສຳ ພັນກັບການເກີດຂື້ນ.

ຄວາມ ສຳ ພັນກັບການເກີດຂື້ນ

Newman – Shanks – Williams ນາຍົກລັດຖະ

ດັ່ງນັ້ນ, ຄົນເຮົາອາດຈະໃຊ້ວິທີທີ່ໂງ່ໆເພື່ອຊອກຫານາຍົກລັດຖະມົນຕີ NSW. ສຳ ລັບແນວທາງທີ່ໂງ່ດັ່ງທີ່ພວກເຮົາສາມາດເຫັນໄດ້ວ່ານາຍົກລັດຖະມົນຕີ NSW ແຕ່ລະຄົນແມ່ນຂຶ້ນກັບນາຍົກລັດຖະມົນຕີ NSW ຄັ້ງສຸດທ້າຍແລະສຸດທ້າຍກັບນາຍົກລັດຖະມົນຕີ NSW ຄັ້ງສຸດທ້າຍ. ສະນັ້ນພວກເຮົາສາມາດ ນຳ ໃຊ້ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ, ບ່ອນທີ່ພວກເຮົາສາມາດເກັບຮັກສາສອງນາທີສຸດທ້າຍຂອງ NSW. ສາເຫດຖ້າພວກເຮົາບໍ່ປະຫຍັດສອງ NSW ຄັ້ງສຸດທ້າຍ. ພວກເຮົາຈະແກ້ໄຂບັນຫາດັ່ງກ່າວເປັນແບບທີ່ເອີ້ນຄືນເຊິ່ງຈະເຮັດໃຫ້ເວລາສັບສົນສັບສົນ. ດັ່ງນັ້ນ, ເພື່ອຫຼຸດຜ່ອນຄວາມສັບສົນຂອງເວລາທີ່ໃຊ້ໃນປັດຈຸບັນກັບຄວາມສັບສົນເວລາເສັ້ນ. ພວກເຮົາຈະຈົດ ຈຳ ບັນດາຄຸນຄ່າເຫລົ່ານີ້.

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບຊອກຫາ Newman – Shanks – Williams prime

#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

ລະຫັດ Java ສຳ ລັບການຊອກຫາ Nh Newman – Shanks – Williams prime

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

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

ໂອ (N), ນັບຕັ້ງແຕ່ພວກເຮົາຕ້ອງການ loop ຈົນກ່ວາພວກເຮົາຊອກຫາ NH ນາຍົກລັດຖະນາຍົກລັດຖະ. ຄວາມສັບສົນຂອງເວລາແມ່ນເປັນເສັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

O (1), ເພາະວ່າຕົວແປໃດກໍ່ຕາມທີ່ພວກເຮົາໄດ້ໃຊ້ໃນການຄິດໄລ່ຜົນໄດ້ຮັບບໍ່ໄດ້ຂື້ນກັບການປ້ອນຂໍ້ມູນ. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ແມ່ນຄົງທີ່.