Build the Trinity Hall Prime

Question

Based on this challenge and this Math.SE question. Idea originally come from a Numberphile video. The goal is to reproduce the logic of Professor McKee when he builds this prime.

Your task is to build the Trinity Hall Prime, at a much lower scale. You are given a single number N greater than 2, representing the length of the prime we need.

Rules

• N is decomposed into a rectangle W(idth) x H(eight). W and H must be close, so 12 is 4x3 and 16 is 4x4 with W >= H
• The first line got only 8's
• The next lines have 8's in the outer and 1's in the middle
• Each lines have 2 more 1's and 2 less 8's than the previous, except if W is odd, then the second line have only one 1 in the middle
• Once you got your emblem, find the first prime greater than the emblem.
• 2 <= N <= 16
• This is ascii-art, so newlines must be part of the output.
• This is code-golf, so shortest code, in bytes, wins.

Test cases:

I   Emblem    O
================
2   88        89

3   888       907

4   88        88
    11        19

6   888       888
    818       827

8   8888      8888
    8118      8133

9   888       888
    818       818
    111       159

10  88888     88888
    88188     88213

16  8888      8888
    8118      8118
    1111      1111
    1111      1159

Answer 1

Python 3, 194 bytes

n=int(input())
R=range
w=n//max(i*(i*i<=n>1>n%i)for i in R(1,n))
m=0
for i in R(n):m=m*10+1+7*(abs(i%w*2-w+1)//2*w>i-w)
while any(m%p<1for p in R(2,m)):m+=1
m=str(m)
while m:print(m[:w]);m=m[w:]

Try it online!

too slow for most inputs, especially x > 8

-6 bytes thanks to Jonathan Frech
-98 bytes thanks to Leaky Nun

Answer 2

Jelly,  57  56 bytes

ŒgṖḊ$€2¦j8
Æd:2‘ịÆDðL€©8,8jÇÐĿḊ€ḣ€⁸Ṛ;®ẋ€⁸¤ḣ:@ðFḌÆnDṁ⁸Gḟ⁶

A monadic link taking a number and returning a list of characters. As a full program it prints the result.

Try it online!

How?

ŒgṖḊ$€2¦j8 - Link 1, previous 8-padded-row builder: list current 8-padded-row
           -                                         e.g. [8,8 , 1,1,1 , 8,8]
Œg         - group runs of equal elements                [[8,8],[1,1,1],[8,8]]
       ¦   - sparse application:
      2    - ...to indices: 2
    $€     - ...do: last two links as a monad for €ach:
  Ṗ        -   pop                                       [[8,8],[1,1  ],[8,8]]
   Ḋ       -   dequeue                                   [[8,8],[  1  ],[8,8]]
        j8 - join with eights                             [8,8, 8, 1, 8, 8,8]
           -   (note: from ...818... this yields an extra 8 - dealt with by ḣ€ in Main)

Æd:2‘ịÆDð... - Main link: number, N
Æd           - divisor count of N
  :2         - integer divided by 2
    ‘        - increment
      ÆD     - divisors of N
     ị       - index into (yields W)
        ð    - start a new dyadic chain with W on the left and N on the right...

...L€©8,8jÇÐĿḊ€ḣ€⁸Ṛ;®ẋ€⁸¤ḣ:@ð... - Main link (continued): W, N
   L€                            - length of €ach of implicit range(W) = list of W 1s
     ©                           - (copy to register for later reuse)
      8,8                        - literal [8,8]
         j                       - join -> [8,1,1,...,1,8] with W 1s
           ÐĿ                    - collect inputs until fixed point:
          Ç                      -   call the last link (1) as a monad
             Ḋ€                  - dequeue €ach (remove the leading 8 from each)
                 ⁸               - chain's right argument, N
               ḣ€                - head €ach to index (remove the trailing 8(s))
                  Ṛ              - reverse
                        ¤        - nilad followed by link(s) as a nilad:
                    ®            -   recall the [1,1,...W times...,1] from the register
                       ⁸         -   chain's left argument, W
                     ẋ€          -   repeat €ach (making W more rows of W 1s)
                   ;             - concatenate
                          :@     - integer division (sw@p arguments) = N:W = H
                         ḣ       - head to index (gets the first H rows - the mask, M)
                            ð    - start a new dyadic chain with arguments M, N

...FḌÆnDṁ⁸Gḟ⁶ - Main link (continued): M, N
   F          - flatten M
    Ḍ         - from decimal list to number
     Æn       - next prime
       D      - to decimal list
         ⁸    - chain's left argument, M
        ṁ     - mould like (reshape like the mask)
          G   - format as a grid (all digits to characters, add spaces and newlines)
            ⁶ - literal space character
           ḟ  - filter discard (Gḟ⁶ instead of Y as single row results are possible)
              - as a full program: implicit print