Одиночные простые числа (как я их называю) - это простые числа, где заданная числовая сетка с шириной w ≥ 3- это простые числа, у которых нет других простых чисел, смежных с ними ортогонально или по диагонали.

Например, если мы возьмем эту сетку, где w = 12(простые числа выделены жирным шрифтом):

1   2   3   4   5   6   7   8   9   10  11  12
13  14  15  16  17  18  19  20  21  22  23...
 ...86  87  88  89  90  91  92  93  94  95  96
97  98  99  100 101 102 103 104 105 106 107 108
109 110 111 112 113 114 115 116 117 118 119 120

Вы можете видеть, что только два простых числа 103 и 107 не имеют никаких простых чисел, ортогональных или диагональных. Я пропустил раздел, потому что там нет одиноких простых чисел. (кроме 37, на самом деле)

Ваша задача состоит в том, чтобы, учитывая два входа w ≥ 3и i ≥ 1определить первое одинокое простое число в числовой сетке с шириной w, где указанное одинокое простое число должно быть больше или равно i. Входные данные могут быть приняты в любом разумном формате (включая их как строки). Гарантируется, что по ширине будет одинокий штрих w.

Сетка не оборачивается.

Примеры:

w  i   output
11 5   11
12 104 107
12 157 157
9  1   151
12 12  37

Поскольку это код-гольф , выигрывает самый короткий код!

C (gcc) , 159 158 149 байт

• Сохраненный байт благодаря xanoetux ; удаление одного символа новой строки.
• Сохранено девять байтов благодаря функциюcatcat ; гольф условия перерыва.

P(n,d,b){for(d=b=1<n;n>++d;)b*=n%d>0;n=b;}F(w,i){w=P(i)&!(P(i-w)|P(i+w)|i%w>1&(P(~-i)|P(i+~w)|P(i+~-w))|i%w>0&(P(-~i)|P(-~i-w)|P(i-~w)))?i:F(w,++i);}

Попробуйте онлайн!

JavaScript (ES6), 116 104 байта

Принимает ввод в синтаксис карри (w)(i).

w=>g=i=>!(C=(k,n=d=i+k)=>n>0?n%--d?C(k,n):d>1:1)(0)&[i,x=1,i-1].every(j=>C(x-w)&C(w+x--)|j%w<1)?i:g(i+1)

Контрольные примеры

let f =

w=>g=i=>!(C=(k,n=d=i+k)=>n>0?n%--d?C(k,n):d>1:1)(0)&[i,x=1,i-1].every(j=>C(x-w)&C(w+x--)|j%w<1)?i:g(i+1)

console.log(f(11)(  5)) // 11
console.log(f(12)(104)) // 107
console.log(f(12)(157)) // 157
console.log(f( 9)(  1)) // 151
console.log(f(12)( 12)) // 37

комментарии

w =>                    // main function, taking w
  g = i =>              // g = recursive function, taking i
    !(                  //
      C = (             // define C:
        k,              //   a function taking an offset k
        n = d = i + k   //   and using n and d, initialized to i + k
      ) =>              //
        n > 0 ?         //   if n is strictly positive:
          n % --d ?     //     decrement d; if d does not divide n:
            C(k, n)     //       do a recursive call
          :             //     else:
            d > 1       //       return true if d > 1 (i.e. n is composite)
        :               //   else:
          1             //     return true (n is beyond the top of the grid)
    )(0) &              // !C(0) tests whether i is prime (or equal to 1, but this is safe)
    [                   // we now need to test the adjacent cells:
      i,                //   right side: i MOD w must not be equal to 0
      x = 1,            //   middle    : always tested (1 MOD w is never equal to 0)
      i - 1             //   left side : (i - 1) MOD w must not be equal to 0
    ]                   // for each value j defined above,
    .every(j =>         // and for x = 1, 0 and -1 respectively:
      C(x - w) &        //   test whether i - w + x is composite
      C(w + x--) |      //            and i + w + x is composite
      j % w < 1         //   or j MOD w equals 0, so that the above result is ignored
    ) ?                 // if all tests pass:
      i                 //   return i
    :                   // else:
      g(i + 1)          //   try again with i + 1

Python 2 , 144 байта

f=lambda w,i,p=lambda n:all(n%j for j in range(2,n))*(n>1):i*(any(map(p,~-i%w*(i+~w,i-1,i+w-1)+(i-w,i+w)+i%w*(i-w+1,i+1,i-~w)))<p(i))or f(w,i+1)

Попробуйте онлайн!

Аргументы в порядке: w, i.

Здесь не используются внешние модули.

Python 2 + sympy, 127 байт

import sympy
f=lambda w,i,p=sympy.isprime:i*(any(map(p,~-i%w*(i+~w,i-1,i+w-1)+(i-w,i+w)+i%w*(i-w+1,i+1,i-~w)))<p(i))or f(w,i+1)

Попробуйте онлайн!

Не заслуживает другого поста, так как единственное отличие здесь в том, что он использует sympy.isprimeвместо реализованной вручную функции первичной проверки.

MATL , 38 байт

xx`@1G*:5MeZpt3Y6Z+>3LZ)ft2G<~)X<a~}2M

Попробуйте онлайн! Или проверьте все тестовые случаи .

объяснение

Код по существу состоит из цикла, который продолжает увеличивать сетку, как описано в тесте, одной строкой на каждой итерации.

После создания сетки на каждой итерации удаляется последняя строка (мы не можем знать, одиночны ли эти простые числа), а оставшиеся числа проверяются на наличие хотя бы одного простого числа. Это делается с помощью 2D свертки.

Если есть какое-то одиночное простое число, мы выходим из цикла и выводим первое такое простое число. В противном случае мы перейдем к следующей итерации, которая будет пытаться увеличить сетку.

(Код фактически использует транспонированную версию сетки, которая увеличивается столбцами, а не строками.)

xx        % Take two inputs (implicit): w, i. Delete them. They get copied
          % into clipboard G
`         % Do...while
  @       %   Push iteration index (1-based)
  1G      %   Push w
  *       %   Multiply
  :       %   Range from 1 to that
  5M      %   Push w again (from automatic clipboard M)
  e       %   Reshape into a matrix with w rows in column-major order
  Zp      %   Is prime? Element-wise
  t       %   Duplicate
  3Y6     %   Push neighbour mask: [1 1 1; 1 0 1; 1 1 1]
  Z+      %   2D convolution, maintaining size
  >       %   Greater than? Element-wise. Gives true for lonely primes
  3LZ)    %   Remove the last column
  f       %   Find linear indices of nonzeros
  t       %   Duplicate
  2G      %   Push i
  <~      %   Not less than?
  )       %   Use as logical index: this removes lonle primes less than i
  X<      %   Minimum. This gives either empty or a nonzero value
  a~      %   True if empty, false if nonzero. This is the loop condition.
          %   Thus the loop proceeds if no lonely prime was found
}         % Finally (execute on loop exit)
  2M      %   Push the first found lonely prime again
          % End (implicit). Display (implicit)

Юлия 0.6, 135 байтов

using Primes
f(w,i,p=isprime)=findfirst(j->(a=max(j-1,0);b=min(j+1,w);c=a:b;!any(p,v for v=[c;c+w;c-w]if v>0&&v!=j)&&p(j)&&j>=i),1:w*w)

У TIO нет Primesпакета. Это на 5 байт короче, если мне разрешено возвращать все одинокие простые числа ( findfirstстановится find). Попытка Джулии вывести функциональность из строя Baseнаносит вред гольфу (не цель Джулии),Primes была включена в 0.4.

Ungolfed (в основном)

function g(w,i)
    for j=i:w*w
        a,b=max(j-1,0),min(j+1,w)
        c=a:b
        !any(isprime,v for v=[c;c+w;c-w]if v>0&&v!=j)&&isprime(j)&&return j
    end
end

Желе , 20 байт

+‘ÆRœ^ḷ,ḷ’dạ/Ṁ€ṂḊð1#

Попробуйте онлайн!

Как это устроено

+‘ÆRœ^ḷ,ḷ’dạ/Ṁ€ṂḊð1#  Main link. Left argument: i. Right argument: w.

                 ð    Combine the links to the left into a chain and begin a new,
                      dyadic chain with arguments i and w.
                  1#  Call the chain to the left with left argument n = i, i+1, ...
                      and right argument w until 1 of them returns a truthy value.
                      Return the match.
+                       Yield n+w.
 ‘                      Increment, yielding n+w+1.
  ÆR                    Yield all primes in [1, ..., n+w+1].
      ḷ                 Left; yield n.
    œ^                  Multiset OR; if n belongs to the prime range, remove it; if
                        it does not, append it.
       ,ḷ               Wrap the resulting array and n into a pair.
         ’              Decrement all involved integers.
          d             Divmod; map each integer k to [k/w, k%w].
           ạ/           Reduce by absolute difference, subtracting [n/w, n%w] from
                        each [k/w, k%w] and taking absolute values.
             Ṁ€         Take the maximum of each resulting pair.
                        A maximum of 0 means that n is not prime.
                        A maximum of 1 means that n has a prime neighbor.
               Ṃ        Take the minimum of the maxima.
                Ḋ       Dequeue; map the minimum m to [2, ..., m].
                        This array is non-empty/truthy iff m > 1.

Perl 6 , 113 104 байта

->\w,\i{first {is-prime $_&none $_ «+«flat -w,w,(-w-1,-1,w-1)xx!($_%w==1),(1-w,1,w+1)xx!($_%%w)},i..*}

Попробуйте онлайн!

Чисто , 181 ... 145 байт

import StdEnv
@w i=hd[x+y\\y<-[0,w..],x<-[1..w]|x+y>=i&&[x+y]==[a+b\\a<-[y-w,y,y+w]|a>=0,b<-[x-1..x+1]|0<b&&b<w&&all((<)0o(rem)(a+b))[2..a+b-1]]]

Попробуйте онлайн!

Ungolfed:

@ w i
    = hd [
        x+y
        \\ y <- [0, w..]
        ,  x <- [1..w]
        | x+y >= i && [x+y] == [
            a+b
            \\ a <- [y-w, y, y+w]
            | a >= 0
            ,  b <- [x-1..x+1]
            | 0 < b && b < w && all ((<) 0 o (rem) (a+b)) [2..a+b-1]
            ]
        ]

Желе ,  30  29 байт

_{Я думаю, что это, вероятно, побиваемо с достаточным запасом}

ÆPŒR+€×¥+©⁸’:⁹Ġ®ṁLÞṪFÆPS’¬ð1#

Двоичное звено, берущее iслева и wсправа, которое возвращает одинокое простое число.

Попробуйте онлайн!

Как?

ÆPŒR+€×¥+©⁸’:⁹Ġ®ṁLÞṪFÆPS’¬ð1# - Link: i, w                     e.g. 37, 12
                           1# - find the 1st match starting at i and counting up of...
                          ð   - ...everything to the left as a dyadic link
                              - (n = i+0; i+1; ... on the left and w on the right):
ÆP                            -   is i prime: 1 if so, 0 if not     1
  ŒR                          -   absolute range: [-1,0,1] or [0]   [-1,0,1]
       ¥                      -   last two links as a dyad (w on the right):
      ×                       -     multiply (vectorises)           [-12,0,12]
    +€                        -     add for €ach       [[-13,-1,11],[-12,0,12],[-11,1,13]]
                              -     - i.e. the offsets if including wrapping
          ⁸                   -   chain's left argument, i
        +                     -   add                  [[24,36,48],[25,37,49],[26,38,50]]
                              -     - i.e. the adjacents if including wrapping
         ©                    -   copy to the register
           ’                  -   decrement            [[23,35,47],[24,36,48],[25,37,49]]
             ⁹                -   chain's right argument, w
            :                 -   integer division               [[1,2,3],[2,3,4],[2,3,4]]
              Ġ               -   group indices by value         [[1],[2,3]]
                              -     - for a prime at the right this would  be [[1,2],[3]]
                              -     - for a prime not at an edge it would be [[1,2,3]]
               ®              -   recall from register [[24,36,48],[25,37,49],[26,38,50]]
                ṁ             -   mould like           [[24,36,48],[[25,37,49],[26,38,50]]]
                  Þ           -   sort by:
                 L            -     length             [[24,36,48],[[25,37,49],[26,38,50]]]
                   Ṫ          -   tail                             [[25,37,49],[26,38,50]]
                              -     - i.e the adjacents now excluding wrapping
                    F         -   flatten                          [25,37,49,26,38,50]
                     ÆP       -   is prime? (vectorises)           [0,1,0,0,0,0]
                       S      -   sum                              1
                        ’     -   decrement                        0
                         ¬    -   not                              1            

Java 8, 176 байт

w->i->{for(;;i++)if(p(i)&!(p(i-w)|p(i+w)|i%w>1&(p(i-1)|p(i+~w)|p(i+w-1))|i%w>0&(p(i+1)|p(i+1-w)|p(i-~w))))return i;}boolean p(int n){for(int i=2;i<n;n=n%i++<1?0:n);return n>1;}

Порт Джонатана Фреха С ответ .

Попробуйте онлайн.