Премьер Ньюмана – Шенкса – Уильямса


Сложный уровень Легко
Часто спрашивают в Хакер Rank
Динамическое программирование Экзамен Математики Простое число Последовательность

Постановка задачи

Простое число Ньюмана – Шанкса – Вильямса (простое число NSW) - это не что иное, как простое число, которое может быть представлено в определенной форме с помощью следующей формулы:

Итак, нам нужно найти n-е простое число NSW.

Пример

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,… (последовательность A088165 в OEIS), соответствующие индексам 3, 5, 7, 19, 29,… (последовательность A005850 в OEIS). {взято из Википедии}

В задаче нам дается просто число n, которое означает, что нам нужно найти n-е простое число NSW. Мы можем найти простое число NSW, используя рекуррентное соотношение.

Рекуррентное отношение

Премьер Ньюмана – Шенкса – Уильямса

Таким образом, можно использовать наивный подход, чтобы найти n-е простое число NSW. Для наивного подхода, поскольку мы видим, что каждое простое число NSW зависит от последнего простого числа NSW и предпоследнего простого числа NSW. Итак, мы можем использовать Динамическое программирование, где мы можем сохранить два последних простых числа NSW. Потому что, если мы не сохраним два последних простых числа NSW. Мы будем решать проблему рекурсивным способом, что приведет к экспоненциальной временной сложности. Таким образом, чтобы уменьшить текущую экспоненциальную временную сложность до линейной временной сложности. Мы запомним эти ценности.

Код:

Код на C ++ для нахождения 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

Java-код для нахождения n-го простого числа Ньюмана – Шанкса – Вильямса

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-е простое число NSW. Временная сложность линейна.

Космическая сложность

O (1), потому что какие бы переменные мы ни использовали для вычисления, результат не зависит от ввода. Таким образом, сложность пространства постоянна.