Простые числа всегда очаровывали людей. 2300 лет назад Евклид писал в своих «Элементах»

Простое число - это то, что измеряется одной единицей.

что означает, что простое число делится только на 1(или само по себе).

Люди всегда искали отношения между простыми числами и придумали довольно странные (как в «интересных») вещи.

Например, простое число Софи Жермен - простое число, pдля которого 2*p+1также простое число.

Безопасный премьер является главным , pдля которого (p-1)/2также простой, что именно условия назад штриха Софи Жермен.

Они связаны с тем, что мы ищем в этом вызове.

Cunningham цепь типа I представляет собой ряд простых чисел, где каждый элемент , за исключением последнего, представляет собой простое Sophie Germain , и каждый элемент , кроме первого является безопасным премьер . Количество элементов в этой цепочке называется его длиной .

Это означает, что мы начинаем с простого pи вычисляем q=2*p+1. Если qпервично тоже, у нас есть оттяжки Каннингхэма цепь типа I длины 2. Тогда мы тестируем 2*q+1и так далее, до следующего сгенерированного число не является составным.

Цепи Каннингема типа II построены по почти одинаковому принципу, единственное отличие состоит в том, что мы проверяем 2*p-1на каждом этапе.

Цепи Каннингема могут иметь длину 1 , что означает, что ни 2 * p + 1, ни 2 * p-1 не являются простыми. Мы не заинтересованы в этом .

Некоторые примеры цепей Каннингема

2начинается цепочка типа I длиной 5.

2, 5, 11, 23, 47

Следующее построенное число будет 95не простым.
Это также говорит нам, что 5, 11, 23и 47не начинать любую цепь типа I , так как он будет иметь предшествующие элементы.

2также начинается цепочка типа II длиной 3.

2, 3, 5

Следующим будет 9, который не прост.

Давайте попробуем 11для типа II (мы исключили его из типа I ранее).
Что ж, 21будет следующим, что не является простым, поэтому у нас будет длина 1 для этой «цепочки», которую мы не учитываем в этом вызове.

Вызов

Написать программу или функцию , что, учитывая число в nкачестве входных, записи / возвращает исходный номер п - й Cunningham цепи типа I или II , по меньшей мере , длины 2 , с последующим пробелом, а затем по типу цепи она начинается ( я или II ), за которым следует двоеточие, за которым следует длина цепи этого типа. В случае, если простое число запускает оба типа цепей (типа I и типа II), цепочка типа I учитывается первой.

Пример: 2 I:5

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

Давайте посмотрим, как это начинается

Начнем с 2. Так как это вообще первое простое число, мы можем быть уверены, что нет цепочки, начинающейся с нижнего простого числа, которое содержит 2.
Следующее число в цепочке типа я был бы 2*2+1 == 5. 5является простым, поэтому у нас уже есть цепочка, по крайней мере, длиной 2.
Мы считаем это первой цепочкой. А как насчет типа II? Следующий номер будет 2*2-1 == 3. 3простое число, поэтому цепочка как минимум длиной 2 для типа II тоже.
Мы считаем это второй цепочкой. И мы сделали для 2.

Следующий штрих есть 3. Здесь мы должны проверить, находится ли цепочка, в которой началось нижнее простое число.
Проверьте тип I: (3-1)/2 == 1. 1не является простым, поэтому 3 может быть отправной точкой для цепочки типа I.
Давайте проверим это. Дальше будет 3*2+1 == 7. 7является простым, поэтому мы имеем цепочку типа I, по крайней мере, длины 2. Мы считаем это как третью цепочку.
Теперь мы проверяем, 3появляется ли в цепочке типа II, что началось нижнее простое число. (3+1)/2 == 2, 2является простым, поэтому 3 не может рассматриваться как начальное число для цепочки типа II. Так что это не считается, даже если следующий 3в этой цепочке номер, который будет5простое. (Конечно, мы уже знали это, и вы, конечно, можете подумать о своем собственном методе выполнения этих проверок.)

И поэтому мы проверяем на для 5, 7, 11и так далее, подсчета голосов , пока мы не найдем п - й Cunningham цепи , по меньшей мере , длиной 2.

Затем (или, может быть, немного раньше ;)) нам нужно определить полную длину найденной цепочки и распечатать результат в ранее упомянутом формате.

Между прочим: в моих тестах я не нашел никакого простого числа, кроме того, 2что запускались оба типа цепочек с длиной больше чем 1.

Примеры ввода / вывода

вход

1

Выход

2 I:5

вход

10

Выход

79 II:3

вход

99

Выход

2129 I:2

Выходы на входы 1..20

2 я: 5
2 II: 3
3 я: 2
7 II: 2
19 II: 3
29 я: 2
31 II: 2
41 я: 3
53 я: 2
79 II: 3
89 я: 6
97 II: 2
113 я: 2
131 я: 2
139 II: 2
173 я: 2
191 я: 2
199 II: 2
211 II: 2
229 II: 2

Список первых 5000 выходов можно найти здесь .

Это код гольф. В выводе допускается произвольный пробел, но тип и числа должны быть разделены одним пробелом и двоеточием, как показано в примерах. Использование любых лазеек не допускается, особенно получение результатов из Интернета не допускается.

Удачи :)

Javascript, 236 208 байт

Сохранено 28 байт:

p=(n,i=n)=>n%--i?p(n,i):i==1;f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:`+eval(`for(j=1;p(k=2*k+l);j++);j`))}

Сохраненные 9 байт на pфункцию с: p=(n,i=n)=>n%--i?p(n,i):i==1
The tфункцией были заменены eval(...)заявлением непосредственно в fфункции.

Предыдущее решение:

p=n=>{for(i=n;n%--i&&i;);return 1==i};t=(n,m)=>{for(j=1;p(n=2*n+m);j++);return j};f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:${t(k,l)}`)}

Пример: f(6)

Выход: 29 I:2

Пояснение
я использую 3 функции

1 p : узнать , простое ли n : p=n=>{for(i=n;n%--i&&i;);return 1==i}

2 t : узнать длину цепи Каннингема, начиная с n типа I или II, в зависимости от параметра m, который будет 1 или -1: t=(n,m)=>{for(j=1;p(n=2*n+m);j++);return j}

3 f : считает цепочки ( для цикла ) и отображает результат

f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:${t(k,l)}`)}

для цикла : для каждого числа действительна цепочка Каннингема (I затем II, если необходимо), если

• число простое
• предшественник не прост
• преемник главный