text:
set intersection of two lists
Your goal is to compute the set intersection of two lists of integers. The intersection is defined as the unique un-ordered group of integers found at least once in both input list.
Input
The input may be in any format desired (function parameter, stdio, etc.), and consists of two lists of integers. You many not assume anything about each list other than they may contain any non-negative number of integers (i.e. they are unsorted, possibly may contain duplicates, may have different lengths, and may even be empty). It is assumed that each integer will fit in your language's native signed integer type, may be more than 1 decimal digit long, and are signed.
Example input:
1 4 3 9 8 8 3 7 0
10 1 4 4 8 -1

Output
The output is any list-like of integers representing the set intersection of the two lists to any format desired (return value, stdio, etc.). There is no requirement that the output be sorted, though you are welcome to provide an implementation that happens to always be sorted. The output must form a valid un-ordered set (e.g. it must not contain any duplicate values).
Example test cases (note that the order of the output is not important):
First two lines are the input lists, third line is the output. (empty) denotes the empty list.
(empty)
(empty)
(empty)

1000
(empty)
(empty)

3 1 2 4 3 1 1 1 1 3
3 1 -1 0 8 3 3 1
1 3

1 2 1
3 3 4
(empty)

Scoring
This is code golf; shortest answer in bytes wins.
Standard loop-holes are prohibited. You may use any built-in features not designed for set-like operations.
Prohibited built-in features:

set creation/removing duplicates
set difference/intersection/union
Generalized membership testing (e.g. anything similar to the in keyword in Python, indexOf-like functions, etc). Note that the use of "foreach item in list" constructs are allowed (assuming they don't violate any of the other restrictions), despite the fact that Python re-uses the in keyword to create this construct.
These prohibited built-ins are "viral", i.e. if there's a larger built-in containing any of these sub-features, it is similarly prohibited (e.g. filtering by membership in a list).

Any built-ins not on the above list are allowed (ex. sorting, integer equality testing, list append/remove by index, filtering, etc.).
For example, take the following two example snippets (Python-like code):
# prohibited: filters by testing if each value in tmpList is a member of listA
result = tmpList.filter(listA)

# ok: filtering by a lambda which manually iterates over listA and checks for equality
def my_in_func(val, slist):
    for a in slist:
        if(val == a):
            return True
    return False
result = filter(lambda v: my_in_func(val, listA), tmpList)

You are welcome to implement any of these set-like features yourself and they will count towards your score.
Your solution should complete in a reasonable amount of time (say, less than a minutes on whatever hardware you have for two lists ~length 1000 each).

By the way, confusion and miscommunication are common in do X without Y, which is why they are officially one of the thing to avoid when writing challenges.

@Dennis Yeah, I guess this problem really has become one of those :( When I first wrote it, I was hoping it might be an interesting problem, but as soon as I started working out a ruleset I should have just killed the challenge.

Is a builtin which performs run length encoding allowed?

That should be fine.

May there be duplicates in the output?

@Nᴮᶻ No, the output is not allowed to have duplicate values, e.g. the output must be a set.

Too restrictive: If you have in your mind one solution... It is not so good....

Haskell, 45 42 bytes
y#(e:s)=[e|any(==e)y,all(/=e)s]++y#s
_#x=x

Try it online!
Edit: -2 bytes thanks to @Ørjan Johansen, -1 byte thanks to @dfeuer.

This is 2 bytes shorter with explicit recursion.

@ØrjanJohansen, 1 more.

MATL, 18 bytes
YY_iti!=Xa)hStdfQ)

Try it online!
This works in two steps. First the intersection is computed, possibly with duplicates. This is based on comparing all elements of one array with all elements of the other, and keeping elements of the first that are present in the second.
Then duplicates are removed. For this, the array from the previous step is sorted, and entries are kept if different from the preceding. A -inf value is prepended so that the first (i.e. lowest) value is not lost.
YY_                 % push -infinity
   it               % take first input. Duplicate
     i!             % take second input. Transpose
        =           % test all combinations of elements of the two inputs for equality
        Xa          % row vector that contains true for elements of first array that
                    % are present in the second, possibly duplicated
          )         % index into first array to keep only those elements. Now we need
                    % to remove duplicates
           h        % append -infinity
            S       % sort
             tdf    % duplicate. Find entries that differ from the preceding
                Q)  % add 1 and index into array to keep only non-duplicates

Jelly, 13 bytes
=S¥Ðf
ṂrṀ{ç³ç

Try it online!
How it works
ṂrṀ{ç³ç  Main link. Arguments: A (list 1), B (list 2)

Ṃ        Yield m, the minimum of A.
  Ṁ{     Yield M, the maxmimum of A.
 r       Create an inclusive range from m to M.
    f³   Apply the helper link with right argument A.
      f  Apply the helper link with right argument B.

=S¥Ðf    Helper link. Arguments: n (integer in range), L (list, A or B)

=        Test all elements of L for equality with n.
 S       Add the results.
  ¥      Combine the two previous links into a dyadic chain.
   Ðf    Filter by the result of the sums.

@isaacg Fixed now.

golflua, 68 chars
\f(a,b)k={}~@_,v p(a)~@_,w p(b)?w==v k[w]=w$$$~@_,v p(k)I.w(v," ")$$

which is called as
> f({1,2,3,4},{3,4,5})
3 4
> f({3,1,2,4,3,1,1,1,1,3},{3,1,-1,0,8,3,3,1})
3 1

In regular Lua, this would be
function foo(a,b)
   local k={}
   for i,v in pairs(a)
      for j,w in pairs(b)
         if v==w then
            k[v] = v
         end
      end
   end
   for i,v in pairs(k)
      print(v," ")
   end
end

So basically I'm iterating over the each element of the two tables and only storing the equivalent values. By using the value as the key (k[w]=w), I'm eliminating all duplicates. We then output the new table by iterating over the index & value of pairs

JavaScript (ES6), 66 bytes
(a,b)=>a.filter((e,i)=>b.some(f=>e==f)&a.slice(0,i).every(f=>e-f))

Without using indexOf, as I'm not convinced that it's permitted.

Pyth, 12 11 bytes
eMrSsq#RQE8

Demonstration
Explanation:
eMrSsq#RQE8
               Implicit: Q is one of the lists.
     q#RQE     For every element in the first list, filter the second list on
               equality with that element.
    s          Concatenate. We now have the intersection, with duplicates.
  rS      8    Sort and run length encode, giving counts and elements.
eM             Take just the elements.

Sorting and rle saves one byte.

@Jakube I would say rle is a builtin which removes duplicates.

It only removes duplicates if you sort it before and remove the counts of the rle afterwards. It's a little bit in a grey area, but I think so is using a dictionary. It's basically a set that stores additional data for each element.

@Jakube OP says it's fine. Thanks!

bash + GNU coreutils, 184 Bytes
[ -z "$1" ] && exit
p='{if(a[$0]++==0)print $0}'
while read A; do
while read B; do
[ $A = $B ] && echo $A
done < <(grep -oP '\d*'<<<$1|awk "$p")
done < <(grep -oP '\d*'<<<$2|awk "$p")

Invocation:
./codegolf.sh '12 4 654 12 3 56' '4 4 56 33 3 3 3'

Output:
4
56
3

No output if intersection is empty.
This script does not sort and makes sanity check if first set is empty. Explanation:
[ -z "$1" ] && exit  # Exit if first set is empty
p='{if(a[$0]++==0)print $0}' # The AWK program we will use
while read A; do   # read the list with two
while read B; do   # encapsulated loops
[ $A = $B ] && echo $A   # if they match, then print
done < <(grep -oP '\d*'<<<$1|awk "$p")
done < <(grep -oP '\d*'<<<$2|awk "$p")
# the process substitution greps the numbers and pipes them to awk. Our awk program makes them unique without sorting; it uses associative arrays with index names same as lines (our numbers here).

Bonus to know: You could change to grep -o . to do this with random strings instead of numbers.

Perl 6, 26 37 bytes
{%(@^a.grep(any(@^b)):p.invert).keys}

usage
> my &f = {%(@^a.grep(any(@^b)):p.invert).keys}
-> @a, @b { #`(Block|559823336) ... }
> f([3,1,2,4,3,1,1,1,1,3], [3,1,-1,0,8,3,3,1])
(1 3)

Cheeky non-competing answer
> [3,1,2,4,3,1,1,1,1,3] ∩ [3,1,-1,0,8,3,3,1]
set(3, 1)

or if you like it in a boring ol' f function
> my &f = &infix:<∩>
sub infix:<∩> (|p is raw) { #`(Sub+{<anon|130874592>}+{Precedence}|102325600) ... }
> f([3,1,2,4,3,1,1,1,1,3], [3,1,-1,0,8,3,3,1])
set(3, 1)

I've updated my answer to not use .unique

You don't really need the invert if you take the values instead. 24 bytes

Retina, 63 bytes
The last two lines remove duplicates. The input is two space-delimited lists separated by a comma. The output is whitespace-delimited.
+`( -?\d+)\b(.*,.*)\1\b
$1_$2
-?\d+\b|_|,

+`(-?\d+)(.*)\1
$1$2

Try it online
If duplicates in the output are allowed, my program would be 42 bytes.

Jq 1.5, 99 bytes
def f(a;b):(a+b|min)as$m|[range($m;a+b|max)|[]]|.[a[]-$m][0]=1|.[b[]-$m][1]=1|.[[[1,1]]]|map(.+$m);

Expanded
def f(a;b):
     (a+b|min) as $m         # find smallest value in either array
   | [range($m;a+b|max)|[]]  # create array of [] for indices [min,max]
   | .[ a[]-$m ][0]=1        # store 1 in [0] at corresponding indices of a
   | .[ b[]-$m ][1]=1        # store 1 in [1] at corresponding indices of b
   | .[[[1,1]]]              # find all the indices where we stored a 1 for a and b
   | map(.+$m)               # convert back from indices to values
;

This avoids using {} objects and since jq does not have bit operations this emulates them with an array.
Try it online!

Axiom, 411 bytes
b(x,v)==(l:=1;h:=#v;repeat(l>h=>break;m:=(l+h)quo 2;x<v.m=>(h:=m-1);x>v.m=>(l:=m+1);return m);0);g(a,b)==(if #a>#b then(v:=a;w:=b)else(v:=b;w:=a);c:=sort(v);for x in w repeat(if binSearch(x,c)~=0 then return 1);0)
f(a:List INT,b:List INT):List INT==(r:List INT:=[];#a*#b=0=>r;x:=sort(a);y:=sort(b);i:=1;repeat(i>#x=>break;v:=x.i;binSearch(v,y)=0=>(i:=i+1);r:=concat(r,v);while i<=#x and x.i=v repeat i:=i+1);r)

ungolf and test
--suppose v.1<=v.2<=....<=v.#v as the default function sort() produce
--   binary serch of x in v, return the index i with v.i==x
--   return 0 if that index not exist
--traslated in Axiom from C  book
--Il Linguaggio C, II Edizione
--Brian W.Kerninghan, Dennis M.Ritchie
binSearch(x,v)==
    l:=1;h:=#v
    repeat
       l>h=>break
       m:=(l+h)quo 2
       x<v.m=>(h:=m-1)
       x>v.m=>(l:=m+1)
       return m
    0

--N*log(N)+n*log(n)+N*n*log(n) so it is N*n*log(n) or n*N*log(N)
ListIntersection(a:List INT,b:List INT):List INT==
    r:List INT:=[];#a*#b=0=>r
    x:=sort(a);y:=sort(b)
    i:=1
    repeat
        i>#x=>break
        v:=x.i
        binSearch(v,y)=0=>(i:=i+1)
        r:=concat(r,v)
        while i<=#x and x.i=v repeat i:=i+1
    r

(5) -> f([],[])
   (5)  []
                                                       Type: List Integer
(6) -> f([1000],[])
   (6)  []
                                                       Type: List Integer
(7) -> f([3,1,2,4,3,1,1,1,1,3],[3,1,-1,0,8,3,3,1])
   (7)  [1,3]
                                                       Type: List Integer
(8) -> f([1,2,1],[3,3,4])
   (8)  []
                                                       Type: List Integer

Axiom, 257 bytes
W(x,y)==>while x repeat y;f(a,b)==(r:List INT:=[];#a*#b=0=>r;x:=sort(a);y:=sort(b);i:=1;j:=1;repeat(j>#y=>break;W(i<=#x and x.i<y.j,i:=i+1);i>#x=>break;W(j<=#y and y.j<x.i,j:=j+1);j>#y=>break;v:=y.j;if x.i=v then(r:=concat(r,v);W(j<=#y and y.j=v,j:=j+1)));r)

This without the use of binsearch... But i don't know the big O...
Unglofed and results:
--N*log(N)+n*log(n)+???
ListIntersection(a:List INT,b:List INT):List INT==
    r:List INT:=[];#a*#b=0=>r
    x:=sort(a);y:=sort(b)
    i:=1;j:=1
    repeat
        j>#y=>break
        while i<=#x and x.i<y.j repeat i:=i+1
        i>#x=>break
        while j<=#y and y.j<x.i repeat j:=j+1
        j>#y=>break
        v:=y.j;if x.i=v then
                        r:=concat(r,v)
                        while j<=#y and y.j=v repeat j:=j+1
    r

(3) -> f([3,1,2,4,3,1,1,1,1,3],[3,1,-1,0,8,3,3,1])
   (3)  [1,3]
                                                       Type: List Integer
(4) -> f([],[])
   (4)  []
                                                       Type: List Integer
(5) -> f([1,2,1],[3,3,4])
   (5)  []
                                                       Type: List Integer

Not executed many tests so could be bugged...

Jelly, 12 bytes
pEÐfḢ€ĠḢ€$ị$

Try it online!

In Tio 3,1,2,4,3,1,1,1,1,3 input and 3 input return the output [1,2,3] instead of [3]

@RosLuP Try [3] instead of 3

It would be ok in my opinion, if the result of intersection of 2 lists return (as other cases) [] if the result is void set, [1] if 2 lists have 1 in common

@RosLuP I can't help it, that's how Jelly does output. Empty for [] and the element for singleton lists. You can go to the wiki page (atoms) and append the Python Stringify builtin but that makes my answer longer and strict I/O is dumb

It would be ok for me  if it accept only input List in [] way (example [1], [1,2,3] [], [ ], [     ] etc) and output the list output only in List [] way (as its input) . If parenthesis for list are {} or () repeat above speech for the right one. This is only for what I think, the question possibly say otherwise and all is ok

@RosLuP Question already says any reasonable format is accepted. This format is reasonable and it's the standard for Jelly. Anything else would be an absurd abomination of our standard rules to prevent languages from not being able to complete.

Husk, 9 bytes
mo←←kIfE*

Try it online!
m            Map
 o←←         taking the first element from the first element
    kI       over lists of identical values from
        *    the Cartesian product of the two input lists
      f      filtered by
       E     both elements of a pair being equal.

Looking in Husk's source code on GitHub, k ("keyon") is implemented as the composition of sorting the list and grouping adjacent values, so although I can't actually find the implementation of "groupOn" it's probably safe to assume that it doesn't do anything setty, since Haskell is a functional language and grouping adjacent equal values is a pretty straightforward reduce-over-a-linked-list operation. (I can find the implementation of k's other type signature "keyby", which I could use here by changing I to =, but I don't know Haskell so I can't tell how exactly it works.)
Also, a nice little Brachylog answer I came up with before I realized set operations of all sorts were disallowed: ⟨∋∈⟩ᵘ

R, 141 83 bytes

l=sapply(strsplit(readLines(file("stdin"))," "),as.numeric)
r=rle(sort(unlist(l)))[[2]]
r[sapply(r,function(x)any(x==l[[1]])&any(x==l[[2]]))]

Improved by Giuseppe
function(a,b){r=rle(sort(c(a,b)))[[2]];r[sapply(r,function(x)any(x==a)&any(x==b))]}

Try online here here

This doesn't seem to work. I'm probably trying to use it wrong, though, so maybe you should supply a link to Try It Online! showing how to use it and demonstrating that it fulfills the requirements of the challenge. (An explanation on the answer wouldn't hurt either.)

you can't assume inputs a and b are pre-defined, you must accept input, either by taking them as function arguments or from STDIN.

I think golfier would be to just make this a function, like this

@d.b The "header" names the anonymous function defined in the "Code" section (anonymous functions are perfectly acceptable), and the footer then calls it. The Header, Code, and Footer sections are all one piece of code, but only the part in the "code" section counts for bytes :-)

Python3, 51 bytes
lambda a,b:[v for v in a if{n:1 for n in b}.get(v)]

If the input lists can contain duplicates:
Python3, 67 bytes
lambda a,b:list({v:1 for v in a if {n:1 for n in b}.get(v)}.keys())

PHP, 78, 77 bytes
function($a,$b){foreach($a as$x)foreach($b as$y)$x==$y?$c[$x]=$x:0;return$c;}

Try it online!
No frills, but rule-compliant (I think).
Output
[], []
[]

[1000], []
[]

[3,1,2,4,3,1,1,1,1,3], [3,1,-1,0,8,3,3,1]
[3,1]

[1,2,1], [3,3,4]
[]


text:
Rotate every row and column in a matrix
The Challenge
Given a n x n matrix of integers with n >= 2

1 2
3 4

and a list of integers with exactly 2nelements

[1,2,-3,-1]

output the rotated matrix. This matrix is contructed in the following way:

Take the first integer in the list and rotate the first row to the right by this value.
Take the next integer and rotate the first column down by this value.
Take the next integer and rotate the second row to the right by this value, etc. until you rotated every row and column of the matrix once.

The list can contain negative integers which means that you shift the row/column left/up instead of right/down. If the integer is zero, don't rotate the row/column.
Example using the input above

List element      Matrix         Explanation
------------------------------------------------------------
1                  2 1           Rotate 1st row right by 1
                   3 4

2                  2 1           Rotate 1st column down by 2
                   3 4

-3                 2 1           Rotate 2nd row left by 3
                   4 3

-1                 2 3           Rotate 2nd column up by 1
                   4 1

Rules

You may choose the most conventient input format. Just make it clear which one you use.
Function or full program allowed.
Default rules for input/output.
Standard loopholes apply.
This is code-golf, so lowest byte-count wins. Tiebreaker is earlier submission.

Test cases
Input format here is a list of lists for the matrix and a normal list for the integers.

[[1,2],[3,4]],[1,2,-3,-1] -> [[2,3],[4,1]]
[[1,2],[3,4]],[1,1,1,1] -> [[3,2],[4,1]]
[[1,2],[3,4]],[0,0,0,0] -> [[1,2],[3,4]]
[[1,2,-3],[-4,5,6],[7,-8,0]],[1,-2,0,-1,3,4] -> [[7,5,0],[-3,-8,2],[-4,1,6]]
[[1,2,-3],[-4,5,6],[7,-8,0]],[3,12,-3,0,-6,-3] -> [[1,2,-3],[-4,5,6],[7,-8,0]]

Happy Coding!

mapcar should help…

CJam, 13 bytes
{{a.m>1m<z}/}

An unnamed block (function) that takes the matrix and the list on top of the stack (in that order) and leaves the new matrix in their place.
Run all test cases.
Same idea, same byte count, different implementations:
{{\(@m>a+z}/}
{{(Im>a+z}fI}
{{:\Im>]z}fI}

Explanation
Ideally we want to treat each instruction in the list the same, and just use it to rotate the first row of the matrix. This can be done quite easily by transforming the matrix after each instruction a bit and making sure that all those extra transformations cancel out in the end. So after processing each instruction, we rotate all rows one up (such that the next instruction along the same dimension processes the next row) and then transpose the matrix, such that we're actually processing columns next. These additional transformations are orthogonal to the instructions in the list and have a period of exactly 2n, just what we need.
As for the code:
{      e# For each instruction...
  a    e#   Wrap it in a singleton array.
  .m>  e#   Combine it element-wise with the matrix to rotate right. This is
       e#   a fairly common idiom to apply a binary operation only to the first
       e#   element of an array, since element-wise operations just retain all the
       e#   unpaired elements of the longer array.
  1m<  e#   Rotate the rows one up.
  z    e#   Transpose.
}/

APL (Dyalog Extended), 17 15 14 13 bytes
-3 bytes by Adám
(⍉1⊖⌽`@1⍢⌽)/⌽

Try it online!
Takes input as a list where the first element is the matrix, and the remaining elements are the rotation amounts. If ⌽ rotated to the right instead of left, this would beat CJam.
(⍉1⊖⌽@1 1⍢⌽)/⌽    Monadic train:
(⍉1⊖⌽@1 1⍢⌽)      Helper function to rotate and transpose once.
                        Takes args ⍺ (amount to rotate) and ⍵ (current array)
     ⌽                 Function to rotate left
        1 1             2-element vector containing 1.
                        The second 1 is redundant, but saves 1 byte over (,1).
     ⌽@1 1             Function to rotate the 1st row left by ⍺.
     ⌽@1 1⍢⌽          Reverse ⍵, rotate 1st row left by ⍺, then reverse again.
                        This rotates the first row of ⍵ to the *right*.
  1⊖                   Rotate all the rows upward,
 ⍉                                                 then transpose.
(⍉1⊖⌽@1 1⍢⌽)/⌽   Fold (/) this function over the reversed input.
                     If our input is ⍵, ⍺_1, ⍺_2, ..., ⍺_2n,
                     the reversed input will be ⍺_2n, ..., ⍺_1, ⍵.
                     The / operator applies the function right to left,
                     so the ⌽ is necessary.

{⍉1⊖⌽⍺⌽@(⍳1)⌽⍵} → (⍉1⊖⌽@(⍳1)⍢⌽) but can you explain to me why @1 won't work instead of @(⍳1) or @(,1)? Also, OP may allow you to take input in reverse.

So it turns out that dfns' at which is behind the extended @ isn't a compatible extension. However, you can use the native @ with \@1which saves a byte over@1 1`.

does rotate work differently in apl vs J ?  i’m trying to translate this to J and finding it a lot more verbose...

Python 2, 96 bytes
def f(m,v):
    for i,x in enumerate(v):x%=len(m);r=m[i/2];m[i/2]=r[-x:]+r[:-x];m=zip(*m)
    return m

Tests
f returns a list of tuples. Each line in the function body is indented with 1 tab character.

Wouldn't a straight return zip(*m) save you 5 bytes?

@DenkerAffe: are you suggesting to replace m=zip(*m);return m with just return zip(*m)? I can't do that because m=zip(*m) is a part of the for loop

Yea, that was my though. Didn't see that its in the loop, my bad.

Stax, 12 bytes
ÄBí•`»O╒┬g½ë

Run and debug it

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Diagram of a leaper
Given an input of a pair of nonnegative integers describing a
leaper in chess,
output a diagram of the squares to which the leaper can move.
From Wikipedia's description:

An (m,n)-leaper is a piece that moves by a fixed type of vector between its
  start square and its arrival square. One of the coordinates of the vector
  'start square – arrival square' must have an absolute value equal to m and
  the other one an absolute value equal to n. [...] For instance, the knight is
  the (1,2)-leaper.

In normal-people-speak, an (m,n)-leaper can move m squares in any direction,
turn 90 degrees, and move n more squares. For example, a (1,2)-leaper (also
known as the knight) can move to these squares:
.E.E.
E...E
..S..
E...E
.E.E.

where S represents the start square, E represents the end square, and .
represents an empty square. This must also be your output for the input 1 2
(and 2 1).
Specifically, the output must

be a square grid with side length max(m,n) * 2 + 1.
contain exactly one S, located in the center of the square.
contain Es at the positions that a (m,n)-leaper at S could move to.
contain dots (.) at all other positions.

You may assume that m ≥ 0, n ≥ 0, m + n > 0, and that m and n are
integers.
Output may be a single string, an array of lines, or an array of arrays of
characters.
Since this is code-golf, the shortest code in bytes will win.
Test cases (all test cases should work with input integers swapped as well):
4 1
...E.E...
.........
.........
E.......E
....S....
E.......E
.........
.........
...E.E...

2 2
E...E
.....
..S..
.....
E...E

3 0
...E...
.......
.......
E..S..E
.......
.......
...E...

1 1
E.E
.S.
E.E

0 1
.E.
ESE
.E.

12 13
.E.......................E.
E.........................E
...........................
...........................
...........................
...........................
...........................
...........................
...........................
...........................
...........................
...........................
...........................
.............S.............
...........................
...........................
...........................
...........................
...........................
...........................
...........................
...........................
...........................
...........................
...........................
E.........................E
.E.......................E.

Javascript, 153 151 bytes
x=>y=>(G=(g,h)=>~[b-x,b+x][X='indexOf'](g)&&~[b-y,b+y][X](h),r=[...Array((b=x>y?x:y)*2+1)]).map((_,i)=>r.map((_,j)=>G(i,j)|G(j,i)?'E':b-i|b-j?'.':'S'))

Ungolfed with explanation:

f=                                     // saves the function in f
    x=>y=>(                            // currying the leaping numbers
        G=(g,h)=>                      // helper function
            ~[b-x,b+x][X='indexOf'](g) // check if g/x is in a goal square by x
                &&                     // and
            ~[b-y,b+y][X](h),          // if h/y is in a goal square by y
        r=[...Array(                   // row or column
            (b=x>y?x:y)*2+1            // of Math.max(x,y)*2+1 squares
        )]                             // stored in r
    ).map((_,i)=>                      // map r with i being the row index
        r.map((_,j)=>                  // for each row map a column with j being its index
            G(i,j)|G(j,i)              // if this square is one possible goal
                ?'E'                   // then 'E'
            :b-i|b-j                   // if is not the middle square
                ?'.'                   // then '.'
            :'S'                       // else 'S'
        )                              // end/next column setup
    )                                  // end function

P.addEventListener('click',_=>(
    a=I.value.split`,`,
    O.innerHTML=f(+a[0])(+a[1]).map(x=>x.join``).join`\n`
));
<input id=I value="1,2"><button id=P>Play</button><pre id=O>

I had a 145 byte answer but the question was closed before I could post it...

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Write a Morse Calculator
Write a program or function that takes a mathematical expression in Morse code as input, and returns the solution in Morse code.
Valid operations are plus: + and minus: _ (underscore). You can assume you will only receive non-negative integer input, and that the result will be non-negative.
The expression will contain at least two terms, and maximum ten terms. There won't be two adjacent operators i.e. .----+_-...., and there won't be parentheses.
Digits are seperated by single spaces. You can choose to have the operators separated from the numbers by a single space on each side (see examples).
The Morse equivalent for the digits 0-9 are:
0  -----
1  .----
2  ..---
3  ...--
4  ....-
5  .....
6  -....
7  --...
8  ---..
9  ----.

Examples:
Input
Output

.----+.----  (1+1=2) Optional input: .---- + .----
..---

-...._...--  (6-3=3) Optional input: -.... _ ...--
...--

..---_...--+..--- (2-3+2=1)
1

..---+...--_....-+---.._.....  (2+3-4+8-5=4)
....-

.---- ..---_-....+...-- ...--  (12-6+33=39)
...-- ----.

----. -----+----.+..--- ----._..... .....+---..+-...._.----+----.+----._..--- -----  (90+9+29-55+8+6-1+9+9-20=84)
---.. ....-

Standard rules regarding I/O formats etc. apply. A few trailing spaces, and a single newline are accepted. You can't split the number over several lines. You can't use eval or equivalent.
This is code golf, so the shortest code in bytes win.

Pyth, 69 63 bytes
J_.:s*R5"-.-"5jdm@Jsd`s*MC,mssdc`MKmxJdcz)"-1"+1mtyq\+@cz)dx_1K

Try it here
Or use a test suite
Explanation
J_.:s*R5"-.-"5                                                  - Construct the morse sequence 0-10
              jd                                                - Prettify output (join by spaces)
                m@Jsd                                           - Get the morse for each character in output
                     `s                                         - Convert to a string
                         C,mssdc`MKmxJdcz)"-1"                  - Get the numbers
                       *M                                       - Multiply the numbers by the operators
                                              +1mtyq\+@cz)dx_1K - Turn `+` and `_` to +-1

Saved 6 bytes thanks to @Jakube!

J_.:s*R5"-.-"5 for constructing the numbers. Probably even shorten when using packed strings.

Retina, 132 bytes
A messy, first pass solution.
(-)+\.+
5$*.$#1$*.
(-|(\.))+ ?
$#2
\d+
$*
+`(1(_)1|(_1+)|_|\+)(.*)
$2$4$3
1+
$.0
\d
$*x5$*-
(x)+x{5}-*
$#1$*-xxxx
(\S{5})\S*
$1
x
.

Try it online!

MATL, 75 71 69 68 bytes
5:t!<t~v45+cXIO1Oj6ZC"@2#0)Iw!Xmfqb+wXK32=?10*}*+K?K9\6-O}V47-Y)Z{Zc

Try it online!
General explanation
I use code format in the following so that indentation expresses the nesting of operations.
The input is split into chunks of 6 characters. The last chunk will have
5 characters padded by a 0 char.
   A 0 is initially pushed. This will contain the accumulated global result.
      Each operand (sequence of digits) is processed as follows. A "sign digit",
      1 or -1, has been previously pushed according to whether the preceding
      operator was + or - (for the first operand 1 is used as sign digit).
      Then a 0 is pushed. This will contain the accumulated operand value.
         Each digit of the operand is transformed into the a number `0`...`9` and
         accumulated to the operand value, with successive multiplications by `10`.
      When a + or - is detected, the current operand is finished. So it is
      multiplied by its sign digit, and added to the acumulated global result.
      A new sign digit is pushed (1 for +, -1 for -), and a new 0 is pushed
      as initial accumulated operand value for the next operand.
   When a 0 char is detected instead of + or -, this marks the end of the input.
   The current global accumulated result is the definitive value. This is
   tranformed into Morse digits and displayed.

Detailed explanation
5:t!<         % first half of the 10x5 array of Morse digits, with 0 for - and 1 for .
t~v           % vertically concat second half, i.e. first half vertically flipped
45+cXI        % transform 0 1 to chars - . Copy this "digit table" to clipboard I
O             % push 0: initial value for accumulated global result
1             % push 1: sign digit for first operand
O             % push 0: initial value of operand
j             % input string
6ZC           % arrange 6-length non-overlapping blocks as columns. Last is 0-padded
"             %   for each column
  @           %   push column
  2#0)        %   split into last element and vector or remaining elements
  I           %   push digit table
  w!          %   swap and transposed into a row
  Xmfq        %   index of that row in the digit table. Subtract 1: gives the digit
  b+          %   bubble up current operand value to top. Add to the new found digit
  wXK         %   swap last char of column (+,-,space,0) to top. Copy to clipboard K
  32=         %   is it space?
  ?           %   if so
    10*       %     multiply by 10. The operand will continue with next digit
  }           %   else: the operand is done
    *         %     multiply by sign digit
    +         %     add this operand with its sign to accumulated global result
    K         %     push last char of column again
    ?         %     if it's not 0
      K9\6-   %       push 1 if it's a +, -1 if it's a -: sign digit of next operand
      O       %       push 0 to initiallize accumulated operand value of next operand
    }         %     else: it's a 0: we're done computing the result
      V       %       convert result to string to get its digits
      47-Y)   %       index the rows of the digit table that was initially pushed
      Z{Zc    %       join rows by spaces
              %     end if, implicit
              %   end if, implicit
              % end for each, implicit
              % display, implicit

Javascript (es6) 236 bytes
plenty of room for improvement
q=>(q.replace(/[.-]{5}/g,q=>(a=q.split`.`.length)&&q[4]=='-'?a-1:11-a).replace(/ /g,'').split(/([_+])/).reduce((l,o)=>l+(+o?(n=='_'?-(+o):+o):(n=o)&&0),0,n='')+[]).split``.map(u=>(((a='.....')+'-----').slice(5-u)+a).substr(0,5)).join` `

broken up

q=>
 (
 //grab each set of 5 dits/dahs
 q.replace(/[.-]{5}/g,

  //count dits
  //if last digit is '-' return dits-1
  //else return 11-dits
  q=>(a=q.split`.`.length)&&q[4]=='-'?a-1:11-a)

   //remove spaces and split on operators + and _
   .replace(/ /g,'').split(/([_+])/)

    //reduce the array into one element
    //start with 0;
    //when we come across a number add it to the total
    //when we come across an operator change current op to it
    .reduce((l,o)=>l+(+o?(n=='_'?-(+o):+o):(n=o)&&0),0,n='')

  //cast to string
  +[])

 //turn to array
 .split``

  //turn each digit back to morse
  .map(u=>(".....-----".slice(5-u)+'.....').substr(0,5)).join` `

usage
f=q=>(q.replace(/[.-]{5}/g,q=>(a=q.split`.`.length)&&q[4]=='-'?a-1:11-a).replace(/ /g,'').split(/([_+])/).reduce((l,o)=>l+(+o?(n=='_'?-(+o):+o):(n=o)&&0),0,n='')+[]).split``.map(u=>(((a='.....')+'-----').slice(5-u)+a).substr(0,5)).join` `

f("----. -----+----.+..--- ----._..... .....+---..+-...._.----+----.+----._..--- -----")

Pure bash, 366 317
a=----- p='v+=($a);a=${a/-/.}';q=${p/-?././-};. <(echo $p{,,,,} $q{,,,,});p(){
[ ${1:0:1} = . ]&&{ b=${1%%-*};o+=${#b};}||{ b=${1%%.*} o+=$[(5+${#b})%10];};}
s=${1//[-.]/};for i in ${1//[+_]/ };do p $i;t=${s:0:1};o+=${t// };s=${s:1};done
r=$[${o//_/-}];for ((i=0;i<${#r};i++));do w+=(${v[${r:i:1}]});done;echo ${w[@]}

Ok, I could save 10 bytes to reach 307 by written 1st line:
v=(----- .---- ..--- ...-- ....- ..... -.... --... ---.. ----.);p(){

instead of (but I like):
a=----- p='v+=($a);a=${a/-/.}';q=${p/-?././-};. <(echo $p{,,,,} $q{,,,,});p(){

Sample:
cat >/tmp/morseCalc.sh <<'eof'
#!/bin/bash
a=----- p='v+=($a);a=${a/-/.}';q=${p/-?././-};. <(echo $p{,,,,} $q{,,,,});p(){
[ ${1:0:1} = . ]&&{ b=${1%%-*};o+=${#b};}||{ b=${1%%.*} o+=$[(5+${#b})%10];};}
s=${1//[-.]/};for i in ${1//[+_]/ };do p $i;t=${s:0:1};o+=${t// };s=${s:1};done
r=$[${o//_/-}];for ((i=0;i<${#r};i++));do w+=(${v[${r:i:1}]});done;echo ${w[@]}
eof
chmod +x /tmp/morseCalc.sh

for test in 1+1 6-3 2-3+2 2+3-4+8-5 12-6+33 90+9+29-55+8+6-1+9+9-20 ;do
    string="$(sed 's/ \.\.\.-\.-$//;s/ \.-\.-\. /+/g;s/ -\.\.\.\.- /_/g' <(
        xargs < <(morse -s -- $test)))"
    out="$(/tmp/morseCalc.sh "$string")"
    res=$(morse -sd <<< "$out")
    echo "$test: $string = $out -> $res"
  done |
    fold -w 80 -s

1+1: .----+.---- = ..--- -> 2
6-3: -...._...-- = ...-- -> 3
2-3+2: ..---_...--+..--- = .---- -> 1
2+3-4+8-5: ..---+...--_....-+---.._..... = ....- -> 4
12-6+33: .---- ..---_-....+...-- ...-- = ...-- ----. -> 39
90+9+29-55+8+6-1+9+9-20: ----. -----+----.+..--- ----._.....
.....+---..+-...._.----+----.+----._..--- ----- = ---.. ....- -> 84

or if morse converter is not installed:
for test in .----+.---- -...._...-- ..---_...--+..---  \
 ..---+...--_....-+---.._..... ".---- ..---_-....+...-- ...--" "----. -----+\
----.+..--- ----._..... .....+---..+-...._.----+----.+----._..--- -----" ;do
    echo $test $(
        bash <(sed '$s/;f/;echo "(${o\/\/_\/-}=$r)";f/' /tmp/morseCalc.sh
            ) "$test" )
  done |
    fold -w80 -s

.----+.---- (1+1=2) ..---
-...._...-- (6-3=3) ...--
..---_...--+..--- (2-3+2=1) .----
..---+...--_....-+---.._..... (2+3-4+8-5=4) ....-
.---- ..---_-....+...-- ...-- (12-6+33=39) ...-- ----.
----. -----+----.+..--- ----._..... .....+---..+-...._.----+----.+----._..---
----- (90+9+29-55+8+6-1+9+9-20=84) ---.. ....-


text:
Permutation Square Root
In math, a permutation σ of order n is a bijective function from the integers 1...n to itself. This list:
2 1 4 3

represents the permutation σ such that σ(1) = 2, σ(2) = 1, σ(3) = 4, and σ(4) = 3.
A square root of a permutation σ is a permutation that, when applied to itself, gives σ. For example, 2 1 4 3 has the square root τ =3 4 2 1.
k           1 2 3 4
τ(k)        3 4 2 1
τ(τ(k))     2 1 4 3

because τ(τ(k)) = σ(k) for all 1≤k≤n.
Input
A list of n>0 integers, all between 1 and n inclusive, representing a permutation. The permutation will always have a square root.
You may use a list of 0...n-1 instead as long as your input and output are consistent.
Output
The permutation's square root, also as an array.
Restrictions
Your algorithm must run in polynomial time in n. That means you can't just loop through all n! permutations of order n.
Any builtins are permitted.
Test cases:
Note that many inputs have multiple possible outputs.
2 1 4 3
3 4 2 1

1
1

3 1 2
2 3 1

8 3 9 1 5 4 10 13 2 12 6 11 7
12 9 2 10 5 7 4 11 3 1 13 8 6

13 7 12 8 10 2 3 11 1 4 5 6 9
9 8 5 2 12 4 11 7 13 6 3 10 1

Would I be correct in saying that for a permutation to have a square root then if it contains n cycles of length m then either n is even or m is odd?

@Neil Yes. Otherwise the permutation can be represented as odd number of swaps.

Ah yes that's a much better way of putting it.

related

Perl, 124 122 bytes
Includes +3 for -alp
Run with the 1 based permutation on STDIN:
rootperm.pl <<< "8 3 9 1 5 4 10 13 2 12 6 11 7"

rootperm.pl:
map{//;@{$G[-1]^$_|$0{$_}}{0,@G}=(@G=map{($n+=$s{$_=$F[$_-1]}++)?():$_}(0+$',0+$_)x@F)x2,%s=$n=0for@F}@F;$_="@0{1..@F}"

Complexity is O(n^3)

Why is the complexity O(n^3)?

@CatsAreFluffy Because it's a stupid program :-). It considers each pair of elements (even if already handled, O(n^2)) and zips their cycles together (not even knowing when to stop, O(n)) then checks if that would be a proper cycle for a square root. In the program you can see the 3 nested loops as 2 maps and a for

Oh. Makes sense.

Mathematica, 165 167 bytes
An unnamed function.
PermutationList[Cycles@Join[Riffle@@@#~(s=Select)~EvenQ@*(l=Length)~SortBy~l~Partition~2,#[[Mod[(#+1)/2Range@#,#,1]&@l@#]]&/@#~s~OddQ@*l]&@@PermutationCycles@#,l@#]&

Semi-ungolfed:
PermutationList[
    Cycles@Join[
        Riffle@@@Partition[SortBy[Select[#,EvenQ@*Length],Length], 2],
        #[[Mod[(Length@#+1)/2Range@Length@#,Length@#,1]]]& /@ Select[#,OddQ@*Length]
    ]& @@ PermutationCycles @ #,
    Max@#
]&

By what magic does this work?

@CatsAreFluffy if I've understood the semi-ungolfed code correctly, it splits the permutation into cycles, groups them by length, then for the odd ones it raises them to the power (length+1)/2 while for the even ones it pairs them up and riffles them together. (If the even cycles can't be paired then the partition has no square root.)

Prolog - 69 chars
p([],_,[]). p([H|T],B,[I|U]):-p(T,B,U),nth1(H,B,I). f(X,Y):-p(Y,Y,X).

Explanation:
permutate([], _, []).                 % An empty permutation is empty
permutate([X|Xs], List, [Y|Ys]) :-    % To permutate List
  permutate(Xs, List, Ys),            % Apply the rest of the permutation
  nth1(X, List, Y).                   % Y is the Xth element of List

root(Permutation, Root) :-            % The root of Permutation
  permutate(Root, Root, Permutation). % Applied to itself, is Permutation

I would imagine this takes exponential time.

Oh, right. I'll have to fix that.


text:
The puppy command
The puppy utility takes a filename as input, and does exactly what you would expect a puppy to do: it shreds it!

How to shred

Rip out the pages with your teeth Split the input file on newlines.
Tear up each page with your paws For each line (not including the linefeed), pick a random integer n such that 2 <= n <= # of characters in the line. Split the line into n non-empty non-overlapping substrings of random length.
Scatter the shreds all over the floor Output each substring of each line to a unique random filename ([a-zA-Z0-9] only, any consistent extension including none, length 1 <= n <= 12) in the current directory. Overwriting pre-existing files within the current directory (including the input file, if it is in the current directory) is acceptable, as long as it does not interfere with your submission running.

Clarifications

There will never be an input where it is possible to use up all of the possible filenames.
Files will consist of only printable ASCII (ordinals 32-127) and linefeeds, and will use UNIX/Linux-style line endings (LF, not the Windows-style CRLF).
A single trailing newline in output files is acceptable as long as every output file has a trailing newline, but is not required. You may choose whether or not the input file contains a trailing newline.
Each line in the input will contain at least 2 characters.
The random values chosen must be chosen from a uniform random distribution on the given set of possible values.

If your language is unable to perform file I/O, you may instead take the input file's contents as input, and output pairs of strings representing the output filename and the text for that file. However, your submission will not be eligible for winning.
Example
Reference implementation:
#!/usr/bin/env python3

import random
import string
import sys

fname = sys.argv[1]
with open(fname) as f:
  txt = f.read().rstrip().split('\n')

for line in txt:
  n = random.randint(2, len(line))-1
  idxs = [0]+random.sample(range(1, len(line)), n)+[len(line)]
  idxs.sort()
  splits = []
  for i in range(0, len(idxs)-1):
    splits.append(line[idxs[i]:idxs[i+1]])
  ofnames = []
  for s in splits:
    flen = random.randint(1, 10)
    ofname = ''
    while ofname == '' or ofname in ofnames:
      ofname = ''
      for i in range(flen):
        ofname += random.choice(string.ascii_letters+string.digits)
    ofnames.append(ofname)
    with open(ofname, 'w') as f:
      f.write(s)

Example run:
$ cat bestsong.txt
Never gonna give you up
Never gonna let you down
Never gonna run around
And desert you!

$ puppy bestsong.txt

$ ls
8675309
a
bestsong.txt
cSdhg
Dq762
jq7t
ret865
rick4life
weu767g
xyzzy

$ cat 8675309
esert you!

$ cat a
Never gonna let you down

$ cat cSdhg
ive y

$ cat Dq762
And d

$ cat jq7t
Never gonna g

$ cat ret865
run arou

$ cat rick4life
Never gonna

$ cat weu767g
nd

$ cat xyzzy
ou up

Related, Related.

'rick4life' rofl

PowerShell v2+, 215 211 bytes
nal d Get-Random;gc $args[0]|%{$b=d(0..($l=($t=$_).length)) -C(d(2..$l));$b=$b+0+$l|select -u|sort;0..($b.count-2)|%{-join($t[$b[$_]..($b[$_+1]-1)])}}|%{$_>(-join[char[]](d(48..57+65..90+97..122) -c(d(1..12))))}

Requires v2 or newer since v1 didn't have Get-Random available.
Edit -- saved 4 bytes by using char-array casting instead of individually casting each letter
Somewhat Ungolfed
Get-Content $args[0]|ForEach-Object{
  $t=$_
  $l=$t.length
  $b=Get-Random(0..$l) -Count(Get-Random(2..$l))
  $b=$b+0+$l|Select-Object -unique|Sort-Object
  0..($b.count-2)|ForEach-Object{
    -join($t[$b[$_]..($b[$_+1]-1)])
  }
}|ForEach-Object{
  $_>(-join[char[]](Get-Random(48..57+65..90+97..122) -count(Get-Random(1..12))))
}

Explanation
Starts with setting d as a New-Alias for Get-Random, so we don't have to type out Get-Random each time we're using it (a lot). We then Get-Content of our input $args and pipe those through a loop with |%{...}. Note that Get-Content will by default split on newlines (either CRLF or just LF), so we don't need to do anything additional there.
Each iteration of the loop, we start with formulating the slices this line is going to be Ginsu'd into. Set $t equal to the line we're working with, and $l equal to its length, then construct a collection from (0..$l). This represents all possible character indices in our current line. We then Get-Random from between (2..$l) to determine how many to select, and then get a random number of indices equal to that -count. Store those indices in $b.
We then also add on 0 and $l to $b, so we have the beginning and end of our line guaranteed to be in the collection of indices. Pipe that through to Select-Object with the -unique flag, then pipe to Sort-Object, so our indices are now guaranteed to start with the first character and end with the last character, and some random number in between.
Next, we're looping over all the indices in $b with 0..($b.count-2)|%{...}. Each of those loop iterations, we're slicing $t (our current line of text) and then -joining them together into a string (rather than a char-array). Those get bundled up and left on the pipeline, and we close the outer loop.
So now we have an in-order collection of random slices of each of the lines of text. (Meaning, at this point, if we simply -joined them back together, we'll get the original text minus newlines.) We then pipe that collection through another loop |%{...} and each iteration we're outputting that slice to a file with $_>.... The file is created by taking from 1 to 12 random integers that correspond with ASCII codes for [0-9A-Za-z]. No file will have an extension, and the > command will output a trailing newline by default on every file.
Example

APL (Dyalog Unicode), 85 80 67 62 bytes
{⍵⎕NPUT(⎕A,⎕D,¯1⎕C⎕A)[?62/⍨?12]1}¨⊃,/{⍵⊆⍨(⍋⊃¨⊂)?⍴⍨≢⍵}¨⊃⎕NGET⍞1

Try it online!
This was a fun one.
Full program which takes a string as input, and outputs files to wherever the ]cd command points to in the Dyalog workspace.
Done with some advice from dzaima.
-13 bytes from Bubbler, by removing ⎕UCS 10.
-5 more bytes from Bubbler after some more smaller golfs and change to the sorting idiom.
Output
Input file is a list of numbers from 1-99 from my "Size Up a Number" challenge.

Explanation
⊃⎕NGET⍞1 read file from location as APL array, take first element, split on newlines. (mode 1)
(last two elements are file attributes)
{⍵⊆⍨(⊂∘⍋⌷⊢)?(/⍨≢⍵)}¨ for each line, execute the following:
            (/⍨≢⍵)   create a list of the length repeated length times
           ?         generate random numbers within those ranges
    (⊂∘⍋⌷⊢)          sort in ascending order
⍵⊆⍨                  partition the line according to the sorted array
⊃,/ join into a single vector and remove nesting
{⍵⎕NPUT(⎕A,(¯1∘⎕C⎕A),⎕D)[?(?12)/62]1} for each partition, do the following:
      (⎕A,             )              create a list with the uppercase alphabet,
      (   (¯1∘⎕C⎕A)    )              the lowercase alphabet,
      (             ,⎕D)              and numbers from 0-9.
                        [ (?12)  ]    generate a random number in range 1-12
                        [     /62]    replicate 62 that many times
                        [?       ]    create that many random numbers in range 1-62, and index into the list.
 ⍵⎕NPUT                            1  write the partition into the random filename, creating it if necessary.

⎕NGET has a mode to auto-split the contents by newlines, so it should work if you replace (⎕UCS 10)(≠⊆⊢)⊃⎕NGET⍞ with simply ⊃⎕NGET⍞1.

Also (/⍨≢⍵) can be ⍴⍨≢⍵ (saving parentheses), (⊂∘⍋⌷⊢) can be (⍋⊃¨⊂) (a variant of sorting idiom that works only with vectors), (?12)/62 can be 62/⍨?12, and you can remove ∘ from ⎕A,⎕D,¯1∘⎕C⎕A.

thanks a lot. @Bubbler

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Stuffing primes in a box
Your task is write a program or function that can fill a given rectangle with
prime numbers. The width and height of the rectangle will be the input. The
output must be a list of height strings consisting of width digits and
spaces. Each horizontal (left to right) and vertical (top to bottom) digit
sequence (delimited by space or rectangle borders) of length 2 or greater must
be a prime number. Each prime number may be used only once. Leading zeros are
not allowed. A trailing new line is optional on the output.
Example:
With input (5, 3) a valid output would be:
11 13
7  0
 173

which scores 11, 13, 173, 17, 103 for a total of 5 points.

Score:
The rectangle size for scoring will be 80, 60.
Each horizontal or vertical prime number of length 2 or more in the rectangle
scores one point. The answer with the most points wins. In the event of a tie,
the earliest answer will win.
Rules:

Standard loopholes are prohibited.
Your program must not be designed for the 80, 60 size. If I suspect an
answer is optimised for this size, I reserve the right to change the rectangle
size up to 100, 100.
The primes used must be real primes (not probabilistic or pseudoprimes). Your program may compute or check numbers at run time, or have them hard coded. The method of finding the primes is not an important part of the challenge.
Your answer should include the output text and your code. If your program is too large, you may just include some core algorithm code, with a little explanation.

Edit: Clarified that real primes needed. Added maximum rectangle size.
Edit 2: Clarified what code needs to be posted.

Are pseudoprimes permitted, or must each claimed prime be unequivocably proven prime?

Normal primes. Positive integers divisible by only itself and one (I did not even know of those other types).

The point of my question is that testing to see whether an 80-digit number is prime takes a long time, but it's quite quick to be able to say that it's prime with probability 99.99999999999999999999999999999%.

For this challenge, you should use regular prime testing. Small primes are likely to be used anyway to maximize scoring.

How are numbers with leading zeroes treated?

Leading zeros are not allowed. No digit sequence in the result set can start with a zero (except zero itself).

In the example output, column 2 contains "1  1".  1 is not prime; see https://en.wikipedia.org/wiki/Prime_number#Primality_of_one.  Or is this sequence considered to mean "11"?

@DavetheSax only integers with at least 2 digits are considered.

@CarpetPython could you clarify "regular prime testing"? Most language's " isPrime" built-ins are probabilistic. Only some languages also come with "isProvablyPrime" built-ins. (Also please edit this requirement into the question, whichever way you decide.)

@MartinBüttner as far as I can tell, with an 80x60 box you'll run out of space before you run out of 4 digit primes (and certainly before you run out of 5 digit primes.) Rigorous prime testing up to this size shouldn't be a problem. 9973 is approximately the 1200th prime. Carpetpython, is it acceptable to write a program that runs best on primes of up to 4 digits?

@MartinBüttner, I was not aware of "probabilistic" prime calculations in such common use. I will edit the question.

@LevelRiverSt, the method of finding primes in not limited, although an algorithm designed for 4-digit primes might be optimised for this puzzle size. I will put a size limit in the challenge rules to clarify what would be considered optimised.

@DavetheSax, this would count as two 1-digit sequences separated by a space. The 1-digit sequences do not have to be prime and they score no points.

I am hoping to see an answer that simply uses an existing crossword puzzle generator function and a list of primes as the word list.

Uh-oh, I've never had a bounty target on my back. But... bring it! ;-)

Clingo with Python, 1600 1689 1740 primes
Approach
I generate a giant constraint satisfaction problem and solve it using an industrial strength satisfiability solver. Lots of magic has gone into making satisfiability solvers relatively fast (even though the problem is NP-complete in general), but fortunately I don’t have to worry about that part.
Specifically, I fix the positions of the digits in a pattern designed for close packing of 4 and 5 digit numbers, with occasional 2 and 3 digit numbers on the boundary, and add constraints saying that each number is a distinct prime.  The current packing uses a large fraction of all 4 digit primes (854 of 1061).
Code
#script (python)

import re

def primesto(n):
    p = [False]*2 + [True]*(n - 2)
    for k in xrange(n):
        if p[k]:
            yield k
            p[k*k::k] = [False]*(-(-n//k) - k)

def main(prg):
    width = prg.get_const('width')
    height = prg.get_const('height')

    primes = list(primesto(30000))
    counts = {4: 4, 5: 4}

    def get_bands(counts):
        if counts:
            for k, v in counts.iteritems():
                counts1 = counts.copy()
                if v == 1:
                    del counts1[k]
                else:
                    counts1[k] = v - 1
                for p in get_bands(counts1):
                    yield (k,) + p
        else:
            yield ()

    def get_img(bands, offset):
        tile = ''.join('#'*k + ' ' for k in bands)
        tile = tile[offset:] + tile[:offset]

        def get_edge(it, corner):
            if not next(it): return True
            if not next(it): return corner
            if not next(it): return True
            if not next(it): return True
            if not next(it): return True
            return False

        def get_cell(x, y):
            return \
                (x == 0 and get_edge((get_cell(i, y) for i in xrange(1, width - 1)), not 1 <= y < height - 1)) or \
                (y == 0 and get_edge((get_cell(x, j) for j in xrange(1, height - 1)), not 1 <= x < width - 1)) or \
                (x == width - 1 and get_edge((get_cell(i, y) for i in xrange(width - 2, 0, -1)), not 1 <= y < height - 1)) or \
                (y == height - 1 and get_edge((get_cell(x, j) for j in xrange(height - 2, 0, -1)), not 1 <= x < width - 1)) or \
                (1 <= x < width - 1 and 1 <= y < height - 1 and tile[(x + y)%len(tile)] == '#')

        img = [[get_cell(x, y) for x in xrange(width)] for y in xrange(height)]

        def get_spaces():
            for y, row in enumerate(img):
                for m in re.finditer('#{2,}', ''.join(' #'[cell] for cell in row)):
                    yield [(x, y) for x in range(m.start(), m.end())]
            for x, col in enumerate(zip(*img)):
                for m in re.finditer('#{2,}', ''.join(' #'[cell] for cell in col)):
                    yield [(x, y) for y in range(m.start(), m.end())]
        spaces = list(get_spaces())

        return img, spaces

    img, spaces = max((get_img(p, o) for p in get_bands(counts) for o in xrange(p[0] + 1)), key=lambda (img, spaces): len(spaces))

    def data():
        for p in primes:
            yield 'prime({}, {}).\n'.format(p, len(str(p)))
            for j, d in enumerate(str(p)):
                yield 'primedigit({}, {}, {}).\n'.format(p, j, int(d))
        for i, space in enumerate(spaces):
            yield 'space({}, {}).\n'.format(i, len(space))
            for j, c in enumerate(space):
                yield 'cell({}, {}, {}).\n'.format(i, j, c)

    def on_model(model):
        digit = {}
        for atom in model.atoms():
            if atom.name() == 'digit':
                c, d = atom.args()
                digit[c] = d
        for y in xrange(height):
            print ''.join(str(digit.get((x, y), ' ')) for x in xrange(width))

    prg.add('data', [], ''.join(data()))
    prg.ground([('base', []), ('data', [])])
    prg.solve_async(on_model=on_model).wait()

#end.

#program base.

1 {loc(P, S) : prime(P, L)} 1 :- space(S, L).
:- prime(P, L), 2 {loc(P, S) : space(S, L)}.
digit(C, D) :- loc(P, S), cell(S, J, C), primedigit(P, J, D).
:- cell(S, J, C), 2 {digit(C, D) : D=0..9}.

#show digit/2.

Usage
clingo -q2 -c width=80 -c height=60 stuff.lp

Warning: at 80×60, this takes about 8 minutes and uses 3 GB of memory.  You may want to start with smaller sizes if you just want to see it running.
Output (80×60, 1740 primes):
13   293 4153 4217 9137   239 3169   223   127   281 9281 9173 4253   257 9239 3
719 28349 2039 7159 4603 17491 6299 17207 19463 19793 3301 4483 5657 20639 10061
 7 26417 7307 2687 9479 14767 3571 10957 21341 14057 5813 6689 2383 19553 2647 3
  15679 6679 6217 1303 19037 5821 11551 18797 28723 3457 6581 5309 12043 4441 2
 14327 4783 5881 6131 21107 2549 12953 24001 12113 7247 9973 8287 16573 5519 149
20177 4967 5647 1907 24439 7237 28979 24781 26083 9859 6691 3701 25237 9041 1637
2953 6781 2851 7079 10139 4001 20981 20341 23531 1913 5081 7639 25169 7457 29437
743 3907 6949 1237 10937 3203 19213 23971 18367 5227 5879 8191 17827 4561 16927
 9 1613 8369 3911 23327 1571 25741 15889 19417 3083 3049 4421 25111 8147 10391
9 9151 3019 3499 11839 5851 23669 16823 14891 9829 9403 1069 26099 8737 21911 2
17389 3217 7963 13337 5779 19841 16007 10313 7673 7703 5897 23911 4409 26737 131
2711 9697 8563 29611 2699 20231 27631 15823 7127 7937 8171 23623 6067 14489 1307
751 2179 7877 12263 7331 17923 26153 11443 7603 1429 8861 28871 8291 20599 20129
 3 3251 5087 28949 4519 22501 15667 28837 2543 3617 2837 15217 4129 20357 29879
2 7507 4127 27479 2521 11423 17497 12409 6599 7297 1249 14813 6301 10501 24151
21487 1777 20143 7109 12239 22063 23761 9931 1579 8929 26641 3221 18251 29429 1
3511 2389 27103 9767 27763 23399 18481 5869 8431 2141 15259 6367 29131 17789 137
941 6719 29269 1811 12829 14929 11953 4817 9787 6469 21377 2473 17033 11311 1453
 3 4549 11491 2777 11351 28879 21061 3607 5441 5861 15493 8941 15101 14437 28579
3 3229 18719 7841 18701 23087 23561 8597 6637 7487 19681 6229 25321 16417 14717
15131 13151 6997 27947 26669 24179 5981 4297 5683 18979 4937 16787 24421 20089
2531 13127 5507 10973 13121 25759 8353 9413 6343 17713 7211 21523 12143 10477 1
107 19381 6871 18803 20117 20849 9091 4051 2333 11399 5987 21617 13147 12281 251
 3 21713 4027 15299 15031 14389 7789 2617 4993 18493 1103 27983 22739 26987 2339
  22853 1297 15959 19531 12799 2269 4943 3917 10093 4657 25999 16603 11617 12919
 14923 1021 15313 11287 14969 1009 2503 9907 25247 4523 16411 12979 22397 8819 7
18191 5039 21019 13619 29947 2087 6793 3529 29671 2861 22259 20921 17291 6703 4
1523 4919 21379 23071 20051 9133 8761 6029 11813 7517 14503 28927 17707 8311 701
311 2939 28183 12347 10357 6143 5437 6011 13789 7573 23629 21773 28703 5059 8609
 7 4799 17333 28069 17921 9803 8543 9601 28151 9059 10457 12119 15661 3593 21937
1 7759 13399 19207 21407 3433 7187 5717 22571 7949 19489 12251 10271 8363 2879 3
13883 10663 20023 12583 1193 5011 1889 20147 4723 25447 15887 29921 4679 7459 4
2887 14341 14759 20593 2267 1567 9901 14411 1229 12041 20483 10889 6163 3517 947
983 24799 13099 13763 4733 9029 5281 17231 6947 29311 22709 11657 2113 8167 2081
 1 24359 29399 11117 2111 9341 9187 25931 7433 20347 16481 17293 5021 8681 17419
  21323 14737 18311 1559 1279 2273 20509 7283 21739 28549 22193 8011 9887 2293 3
 21011 19231 16127 6197 5107 7151 21013 2551 22943 28057 13229 9277 7229 1721 1
19927 22549 20641 8053 6529 5737 29021 1483 23027 24977 17623 3347 6791 1213 157
8573 23447 24499 4273 8963 6257 21881 3343 27329 17627 28307 2393 4493 3613 1117
167 15991 17029 2803 6673 3797 28219 4621 22277 12071 13043 6661 6323 8297 19433
 7 24517 11777 1609 9941 2437 26189 8831 10771 11467 24091 2371 3331 7607 14947
  22727 13967 1471 7451 1367 11113 7477 11527 24007 23557 1277 4969 6829 28097
 12073 11887 3181 8999 5641 13411 7321 22901 28001 20939 3889 5231 8863 26357 3
20011 23671 5669 1291 9421 12689 4903 21647 19483 12157 4861 5381 9067 11471 283
2663 22123 2833 1663 8677 19891 8039 19141 23321 17417 2027 9949 6389 23459 7351
967 15901 1831 1013 5527 12697 5573 16547 14029 23333 3623 9007 6047 12739 18539
 7 14369 9719 6199 7499 20663 3413 23339 25097 12973 9791 9643 2459 18353 9371 1
  16843 8329 1451 5279 13441 9433 27647 28643 12007 4463 6269 7523 22861 6899 1
 18143 5743 2591 4211 27551 9461 27689 11279 14533 2731 3001 6857 13757 3259 277
22483 3943 9011 8933 18593 6569 26891 22381 22109 4721 1733 2377 11549 5387 1459
6203 5351 9851 6133 29573 4513 28517 14083 15773 3109 9967 5113 29063 1427 17257
911 8713 8783 9613 27253 3851 25537 16993 17683 3037 4007 5651 12487 6779 26251
 1 7243 3023 4751 10459 4931 25639 25867 12101 6373 4201 8123 15227 7589 10601
1 9631 1061 1549 10159 1381 18047 26687 20411 2129 2011 1583 12899 9749 26339 1
25127 3389 4013 15647 1669 25933 24443 21557 7853 3449 6089 28771 1847 21491 263
8501 2309 2797 16189 2003 22637 15973 28697 2741 2729 1361 25667 2131 23633 2297
359 9551 6553 11597 6451 20123 10259 29287 5923 8233 1423 10133 1373 23773 11633
 7 5119 7829 24019 7691 12479 14143 20873 5323 1493 3709 18947 5701 12413 27997
4 3697 5261 17359 1657 26371 20443 11239 4093 7013 5303 15767 4259 13499 13597 5
31 3919 7393 199   9397 379   971   193   3319 1979 1931 173   3391 937   397 19

Any explanation?

yes, you should write that (maybe with a few more details) in the answer

Added some explanation.

I went cross-eyed trying (and failing) to decipher what you're doing there, but very nice, and probably dang nigh impossible to beat. Unless... (Scuttles away to think up a new approach.)

You have the number 9463 twice... and 27687 isn't actually prime.

I see a "1" at the top over there, just below the 239 at the top row

@AmosM.Carpenter: Although I am aware of the current date, I did go and check: 9463 is there once and 27687 is not there.

@proudhaskeller: The challenge author was very clear that only digit sequences of length 2 or greater are considered.

@AndersKaseorg: Sorry, couldn't resist - hope I had you there for a second. ;-) Seriously, though, great answer, and well deserving of the bounty. I have another approach, but haven't had enough time to work on it all week. I'll have a go now, but doubt I'll get it ready by the time the bounty period expires, so well done and congrats.

Oh, and since my second "April Fool's answer" was mercilessly and humourlessly deleted last night, probably before you got a chance to see it... I think I spotted an improvement to your matrix, which looks like it doesn't actually use the prime 11. If that's correct (haven't tested, just looked), you could turn 193 in the bottom row into 1193 to make one more prime (11) with the digit above it. Cheers!

A clever algorithm with a good result. I think it would be hard to beat this. Thanks for your answer +100!

Smalltalk, 1098 primes
First off, nice hard question - as evidenced by the lack of non-trivial responses thus far.
I had a solution cooking at work, but had to wait for the long weekend to have time to clean it up a bit. Even so, it's quite "heavy", so excuse the length of this answer - thankfully this isn't a code-golf question. There were plenty of little gotchas along the way, but I'm pretty sure it's bug-free now, though there is plenty of room for improvement and fine-tuning.
Language
My language of choice for this sort of thing is Smalltalk - the superior debugging and the ability to test-as-you-code beats anything else I know. Plus, even non-coders can read it and understand the basics of what's going on. I've limited the code below to the interesting part, because I thought the approach and results would be more interesting than the boilerplate code, but a file-out of the full code is pasted here if anyone wants to try it out (just save as a *.st and file it in from a file browser in Pharo). I used Pharo 4.0, which is FOSS and can be downloaded from pharo.org for Win/Mac/Linux. Also happy to paste the full code here, but I took the "should include the output text and your code" as a suggestion - let me know if I'm wrong.
Approach
So, my thinking was, what if you could start in the middle, stuff as many long primes as you could in the box, and work your way outwards from there? Let's start with a Box object, containing a matrix of characters, and then use a Stuffer object to try to fill it up by finding the best Insertion (another object) for each point in the matrix and for each prime (starting with the long ones). Pharo has nice Matrix and Point classes with a bunch of useful methods (though the matrix way of using row-major notation versus using x-y-coordinates of points can get a little confusing if you're not careful).
The basic steps of my algorithm are:

Create a Stuffer instance for given dimensions.
Have the stuffer initialise its box to size 5x5 (unless dimensions
are smaller).
Ask the Stuffer to stuff its box.

Iterate over a list of primes from largest to smallest.
Iterate over all points in the matrix.
Find the best spot to insert the prime, and insert if possible.

While the box can "grow" (until the target dimensions are reached),
increase it by one row/column on each side and copy the old contents
into the middle of the bigger one, then go to step 3.

Configurable:

The dimensions
The largest prime to start from
The "rating" of insertions (when choosing from multiple possible places to insert a prime)

For the matrix below, I used 80x60, primes below 20,000 (since the combined length of those is just under 10,000 characters, i.e. the maximum for a stuffed, though invalid, 100x100 box), and, after some experimentation, the following rating for each insertion:
(each accidentalPrimes size * 1) + (each numberOfOverlaps * 2)

where accidentalPrimes are the perpendicular primes "accidentally" created when inserting between neighbouring primes, and numberOfOverlaps is how many characters are overwritten (e.g. when adding a 3 at the end of 11 to insert 113). I initially had it weighted more towards accidentalPrimes, but got a few more primes in the box by doing it this way - not entirely sure why (feel free to test/tweak).
Result
| 1  3449 8    19489 8 7 9277 2 7 419  6   9533   19211    19373 4  79379 9 6 1 1|
|8861 1 7 26701 6   19219 6  97577 6 319211  84631   3 9649  8  19207 6 7 10399 9|
| 7 8 98669    19469 5 0  19301 2 6997 4   9787   19441  7 18899 9  2 47297 1 0 0|
|8839 8 7  1613 5 6  149837  0 97213 319289  6 8291  915991 431  909113 1 3382373|
| 7 7607 1 9 9 19543  1 8  3779   5743  6 19813  1946981    19423  139 9 9431 1 1|
|  6911 8933 2 9  9 1 4198013  9497   19447    1093 9 1194899 8  569 4 487749433 |
|  1 1 1 3 0 5653 19583 5  101429 4691  4 119813 9923  9 5 9  1811 47293 3533 1 1|
| 8849 8 86959 0 1  0 4 195071 7589 19429 5 1  4    3863 219763  9 2 1 9391 87833|
|  9 813613 7  719 19471   6 19727 809 7 19759 619867 6 988069 1 5 11 191 9 1 9 8|
|541 0 7 3547 1  70919 93715816451 19609 3  6  3 41  757219717 9803 9 9 9283  4 7|
|  3 1 9  1  691 6 4 177493124562997 7 1 719483  152993 8 9 6173 7 4871 0 7 15797|
|5171 373 9 1 4  318191 263 19843  19919  8 19889953 4  169639 9679 6 8887  9    |
| 8 8 1  5449 2 9 9399647333  7907  8 8 677   2 6 6 9967 101 8111 7 7 3 7 1907 1 |
| 7 67901 2 2 757 8 5 9 119759 7499 19853 19751 19913  59879 0  6469 171179 6 487|
|8747 0 9 78167 4 8 78839  6 99317  1 3 9 9 9   9  16993 7 8117 3373 9 9  8093 9 |
| 3 913457  31193 9 107 7 198439   9 19861 19697  99125471 1   16979 2819 0  9 1 |
|9 1951 0 1879 1 7 1 1 6569 853 18397  83 8 656269159547193329 97871 7 2  1 4337 |
|14831 9157 6449 0 9 9613 8 15619 148436196977821 19597 9 9 6907 8 383 16573 1  1|
|7 9 8   4518803 15647 9 941 19661 19963 149 19937  43913 2393 1433   1 1 1 9 9 8|
|3 1 3613719596827 8 2 6 5163998629 467 6271    13967 29399 51673 9 15973 87473 9|
| 9127 9  927191 19157 0 8 66938969 176597 19949 5779513 1319 6 92779 14717 3 7 1|
| 1  98849 8  9  9  8  3371771169929  169937 4 65519 79769 9 906473 58699 9 78173|
| 8    0 6 9907 682771709 9  9 3319763 947387669 479978309 8597 35393 369731 5   |
| 6211 1823 1 318691 96918839 9 19 918481 1997911733 58271 6 2 9 1  1  92219 661 |
| 7 8 7349  9 369739 7297 1 8641 4 12983    6 61991 619793 7 3 8297  15791 0 3   |
| 9 8 1 1 1 5  619 8 510589 396932999 7 5897537 997379 6   39313 4 439 69911   1 |
|1  64969 9 54139 7069 739 99639719 58693 4951 977   9 9151 8 9 6689 257 4 37199 |
|8  9 0 37529 9 4 91193  6 6 9 7  6 8 11117 3970331  11969963 661911661 727  9 3 |
|3613 0 8 5   3 2 8 9 1 499787 9137 71 19997 971939 13999 787 0 9 9  701 7 151 8 |
|7 8 6961 97607 1 15569 9 8 1 1 1171 99929 99733 1759 9817931 3 8941  193  968819|
|9 8 0 6    0 99767 8 769 88969 9859 979871393 1733 9377113 95111 5  8 2 94033  1|
| 9041 6 14519   1063 6 937 8 8 8999 92993171 11519 313 89417 7 317 5233 4 3  9 8|
|433  8179 6113 8971  3191 7559 17 63313 939793919 971 198769 5693 9 7 14657  6 7|
| 9  1  725189 1 7591139 9 93911 3919 9257 33739 9293 29 1973 2  9161 9511  17239|
|349 87151 99349 57529 7 36637 6359 81999119371933 4 98573 7549 6317 6619 8 9 3 3|
| 3  8 99371 8 8 374718269 1144935789717977  83177 9 233  1499 8 1571 4 8 6803 9 |
| 9 15641  3 1607  3 8 761 393388937 9    3967  9 9719 13997 1259 7 9639079 0 443|
|  1 9 2 14969 1109 8313931 8  198174119963 5 997 9 9 991 8 1217 52579  1 3911 1 |
|5281 277    1979 32909 9 986983 19991  61399991 127997 9 82939 907 571847 4 9 3 |
|  7 8  9 617 8 4 21613 2 95792383  919979 4951997317 93719 4 641379379 1 12487  |
|1 9 66959 8  8 4 3339313613 5119963  189967 359 337361 25933 83891   8 8191 7  1|
|8 7 8 61516883 1619 839 799859 2 7 19927 5 19777 6737 9769 37799 9 19079 0 9 1 9|
|57331 2 4 9 1 1  7691 9697 61 19577 6 9949 9 9 31979399 1 1 8737 509 1 49871 8 8|
|9  1 6397 109 99133 3 313888397 59419699  1986133  8387 9 988319 5 47237 7 8 9 0|
|3  62131 1  38629 8699 9 8599 953 397   736903  1991933 877 3 4799 1 1     77171|
| 1 8 8 9091 7 86491  627673 593 1  19853377 9781  8  3 76919  7  49739 1511  9  |
| 8 76991 0 938747 9 924629743 193873 2 699823 8719801 907871 19181   4 9 9 93371|
|6959 7 88867 6 7757 792383  8 9  0  1981337 3947  3 3917 2089979 9 92831 0 4 2 8|
| 4  5953 1 3739   69473 7 19709 99016787  379 9619759 196991 6 56393 9 3 82373 9|
|273613  1163  13883 919531 8  7433 6337 8893 6917   9 9 1693 8 0 7 709 93199 9 1|
|631 97159 8  181 9 6   0 0 7819753 673  9    9  9901 19699   18119 7  1 1 111779|
|9 8 0 9 0 2 7919 4419559 98179  6  9  19553 9851 4 9 9067 9857 4957 14939 9397  |
| 8753 0 3631 4 4 18973 9 7  89923 19793 1 8  3491954199497 53 2969  9 0 0 0 0 6 |
|1 9 1 5 1    5 24337 9  19603 7 9 3  4 195312373619977 9 119489 8 96293 643 0 4 |
|8 3   18461  7577 1 19541 8 3929 19463 6  3 49937 3 9 98297 71347 3 4 7 9 1 9 1 |
|87541   9 92707 9817  2 58237 1 4 6  919423 5    19403 77383 194179 9601 1 1 1 1|
|6 9 38923 4 261631 61937389 19387 390739 9 19319 6 495617 9 5  9  7  93979 8 8 8|
|9 449 5 4658147899073 7  3   60293 5  7 8231 2641930937 7 1950139511 6 0 26993 7|
|  0 0 2 34789739 1 3619501   61930959767 7 19237 7 9 9829   7    7   27773 5 7 5|
|823 7211 7 3 3 919231     9631 337 1  3    7 9 3      1 3943 19141 653 3 15971 7|

This matrix contains 1098 primes, which is a "load" of about 70%.
These are the primes (box primesUsed asSortedCollection printString):
11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 107 109 113 127 131 137 139 149 151 163 167 173 179 181 191 193 197 199 233 257 263 269 271 277 283 293 307 311 313 317 331 337 347 349 359 367 373 379 383 389 397 419 431 433 439 443 449 467 479 487 491 499 509 541 547 557 563 569 571 577 587 593 599 601 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 1063 1093 1109 1117 1153 1163 1171 1181 1217 1259 1319 1361 1399 1433 1499 1511 1571 1607 1613 1619 1637 1663 1667 1693 1697 1699 1733 1759 1811 1823 1879 1907 1913 1933 1949 1951 1973 1979 1987 1993 1997 1999 2393 2459 2617 2819 2927 2939 2969 3191 3229 3343 3373 3389 3449 3533 3539 3547 3613 3617 3631 3643 3733 3739 3769 3779 3793 3797 3821 3863 3911 3917 3919 3929 3931 3943 3947 3967 3989 4337 4409 4493 4691 4799 4871 4951 4957 4967 4999 5039 5099 5101 5171 5233 5281 5347 5399 5449 5479 5653 5693 5743 5939 5953 6079 6113 6131 6173 6197 6199 6211 6271 6317 6337 6359 6397 6449 6469 6569 6571 6599 6607 6619 6653 6661 6689 6737 6779 6781 6793 6803 6823 6829 6899 6907 6911 6917 6949 6959 6961 6967 6977 6997 7069 7079 7109 7193 7211 7219 7229 7297 7307 7349 7393 7433 7499 7549 7559 7577 7589 7607 7621 7691 7727 7757 7883 7907 7919 7949 7951 8093 8111 8117 8171 8179 8191 8219 8231 8291 8293 8297 8387 8419 8537 8539 8563 8597 8599 8641 8647 8681 8689 8693 8699 8719 8737 8747 8753 8779 8831 8839 8849 8861 8863 8887 8893 8929 8933 8941 8951 8963 8969 8971 8999 9007 9041 9067 9091 9109 9127 9137 9151 9157 9161 9173 9181 9187 9199 9257 9277 9281 9283 9293 9371 9377 9391 9397 9413 9419 9421 9431 9437 9461 9463 9467 9473 9479 9491 9497 9511 9521 9533 9539 9547 9551 9587 9601 9613 9619 9623 9629 9631 9643 9649 9661 9677 9679 9689 9697 9719 9721 9733 9739 9743 9749 9767 9769 9781 9787 9791 9803 9811 9817 9829 9833 9839 9851 9857 9859 9871 9883 9887 9901 9907 9923 9929 9931 9941 9949 9967 9973 10399 10979 11117 11519 11939 11959 11981 12487 12983 13313 13339 13463 13499 13763 13877 13883 13907 13931 13963 13967 13997 13999 14519 14657 14717 14831 14939 14969 15091 15569 15619 15641 15647 15791 15797 15971 15973 16573 16699 16937 16979 16993 17239 17333 17519 17761 17891 18119 18371 18379 18397 18461 18593 18691 18719 18757 18773 18787 18803 18839 18859 18869 18899 18911 18913 18917 18919 18959 18973 18979 19001 19009 19013 19031 19037 19051 19069 19073 19079 19081 19087 19121 19139 19141 19157 19163 19181 19183 19207 19211 19213 19219 19231 19237 19249 19259 19267 19273 19289 19301 19309 19319 19333 19373 19379 19381 19387 19391 19403 19417 19421 19423 19427 19429 19433 19441 19447 19457 19463 19469 19471 19477 19483 19489 19501 19507 19531 19541 19543 19553 19559 19571 19577 19583 19597 19603 19609 19661 19681 19687 19697 19699 19709 19717 19727 19739 19751 19753 19759 19763 19777 19793 19801 19813 19819 19841 19843 19853 19861 19867 19889 19891 19913 19919 19927 19937 19949 19961 19963 19973 19979 19991 19993 19997 21613 24239 24337 25933 26449 26701 26959 26993 27773 27919 29399 31193 32909 33739 35393 36637 36761 37199 37529 37799 38333 38629 38839 38861 38923 39293 39313 39733 43913 43943 45281 47237 47293 47297 47933 47939 48311 48761 49123 49199 49739 49871 49937 49999 51193 51673 52379 52579 54139 55313 56393 56983 57173 57331 57529 58237 58271 58693 58699 59743 59879 60293 61979 61991 62131 62873 63313 64969 65519 66491 66959 67339 67901 67993 69337 69473 69623 69697 69911 69941 70919 71347 71777 71933 75347 76163 76733 76919 76991 77171 77213 77383 77591 78167 78173 78839 78941 79379 79613 79631 79769 79967 80933 81919 82373 82939 83177 83891 84631 86491 86959 87151 87473 87541 87833 88499 88867 88951 88969 89413 89417 89519 89923 91193 91813 91997 92219 92593 92647 92707 92779 92831 93199 93371 93719 93911 93913 93971 93979 94033 94397 94399 95111 96233 96293 96587 96911 96959 96979 97159 97213 97577 97607 97787 97871 97919 98179 98297 98299 98573 98669 98837 98849 99133 99233 99317 99349 99371 99497 99733 99767 99907 99929 101429 111149 111779 119489 119759 119813 127997 149837 152993 167747 168863 169639 169937 171179 176597 179099 179111 183797 187973 188693 189473 189967 190811 191837 193813 193873 194179 195071 195319 196817 196871 196991 197273 197599 198013 198017 198439 198673 198769 199373 199679 199739 219763 261631 273613 277793 316879 318191 318691 319031 319069 319211 319289 319427 319727 319973 337361 369731 369739 390739 391753 414347 419801 439883 495617 499787 510589 519031 571847 601189 615749 616367 618719 619543 619583 619753 619763 619793 619813 619867 627673 639631 669923 698339 699823 716987 719009 719441 719483 719801 719813 725189 736903 792383 796553 799859 809339 813613 815569 819373 819457 829733 906473 907871 909113 912797 913457 914813 915641 915991 917159 918481 918679 918793 919183 919231 919381 919421 919423 919531 919559 919913 919979 927191 935639 938747 939439 943913 962971 968819 971939 976777 986983 988069 988319 991733 997319 997379 1194899 1518379 1678739 1691189 1867993 1899907 1903703 1923151 1942771 1946981 1950149 1981337 1986133 1988999 1991933 2089979 2919031 3110651 3190871 3193913 3197633 3319763 3382373 3619501 3970331 4198013 4419559 4518803 5119963 5195077 5319289 5619139 5779513 5897537 6119801 6129587 6189137 6194891 6198139 6649871 7219427 7591139 7819753 7937939 7982969 8019727 8313931 8419381 8719801 8783371 9119909 9189797 9323173 9377113 9619759 9639079 9679799 9717317 9721301 9721991 9817931 9911789 9923369 9967759 11969963 15619867 16981331 19669931 19717099 19793479 19853377 19889953 21968773 27519469 31979399 34789739 40699733 59419699 61399991 61516883 61897937 61937389 63519427 66938969 69719801 74969767 91938191 92993171 93369931 95792383 96918839 99016787 99125471 99639719 126919421 179319979 199733981 199739717 313888397 342719753 374718269 393388937 396932999 439314797 479978309 487749433 577519913 613799299 631819381 641379379 661911661 682771709 689194217 757219717 924629743 936195479 939793919 947387669 979871393 991579637 1903149343 1921376857 1945706473 1950139511 1960317529 1997911733 2641930937 3339313613 4951997317 4952523041 5163998629 7017198679 7981707577 9013119991 9119993297 9399647333 9945519919 18919323977 19031318947 19919788793 31879359403 61930959767 61960309907 91734751987 92774649739 93715816451 95479219889 98371979359 99551395387 191830198139 198012194899 198017187931 198174119963 213963819763 419801418947 819853319867 1937327699987 3189735598139 3371771169929 3491954199497 3613719596827 4658147899073 81999119371933 148436196977821 177493124562997 195312373619977 1144935789717977 656269159547193329 735547997331319937 11572771955941937959

As you can see, some of the "accidental" primes get quite long... 20 digits for the longest one. :-)
Details
To understand how it works, here is the output from doing the first few steps - inserting 19997 first (if you look in the middle of the big matrix, you'll see 19997 there as well), then down the list where there's space in the 5x5 box (> means insert going right, v means going down; anything in {} are accidentally added primes:
Insertion at: (1@1) > {} of 19997
Box 5x5 (1 prime, load: 20%):
|19997|
|     |
|     |
|     |
|     |

Insertion at: (1@1) v {} of 19993
Box 5x5 (2 primes, load: 36%):
|19997|
|9    |
|9    |
|9    |
|3    |

Insertion at: (3@1) v {} of 9973
Box 5x5 (3 primes, load: 48%):
|19997|
|9 9  |
|9 7  |
|9 3  |
|3    |

Insertion at: (1@4) > {} of 9931
Box 5x5 (4 primes, load: 56%):
|19997|
|9 9  |
|9 7  |
|9931 |
|3    |

Insertion at: (1@3) > {89, 11} of 9871
Box 5x5 (7 primes, load: 64%):
|19997|
|9 9  |
|9871 |
|9931 |
|3    |

Insertion at: (5@1) v {98713, 99317} of 7937
Box 5x5 (10 primes, load: 76%):
|19997|
|9 9 9|
|98713|
|99317|
|3    |

Insertion at: (4@3) v {} of 113
Box 5x5 (11 primes, load: 80%):
|19997|
|9 9 9|
|98713|
|99317|
|3  3 |

11 old primes: 19997, 19993, 9973, 9931, 9871, 89, 11, 7937, 98713, 99317, 113
8 new primes: 19997, 98713, 99317, 19993, 89, 9973, 113, 7937
Insertion at: (4@1) v {} of 19973
Box 7x7 (9 primes, load: 42%):
|   1   |
| 19997 |
| 9 9 9 |
| 98713 |
| 99317 |
| 3  3  |
|       |

In the insertion immediately above, the box becomes a 7x7, and is filled with the 5x5 contents before the next insertion happens. I also re-calculate the primes used at this point, because some are "freed up" due to overwriting (11 was inserted, but then overwritten by 113).
Code
Here are the most relevant parts of the code:
Stuffer class
Class side
forDimensions: aPoint
    ^self new
        width: aPoint x;
        height: aPoint y;
        initializeBox;
        yourself

Instance side
initializeBox
    box := Box width: (width min: 5) height: (height min: 5)

stuffBox
    self stuffCurrentBox.
    [self canGrow] whileTrue: [
        box growMatrixByOneUpTo: width @ height.
        self stuffCurrentBox
        ]

canGrow
    ^width > box width or: [height > box height]

stuffCurrentBox
    self class primes reverseDo: [:eachPrime |
        | string insertion |
        (box primesUsed includes: eachPrime) ifFalse: [
            string := eachPrime asString.
            (insertion := box bestInsertionFor: string) ifNotNil: [
                Transcript crShow: insertion printString, ' of ', string.
                box doInsertion: insertion of: eachPrime.
                Transcript crShow: box
                ]
            ]
        ].
    box updatePrimesUsed.

Box class
Instance side
bestInsertionFor: aString
    | insertions |
    insertions := OrderedCollection new.
    self pointsDo: [:eachPoint |
        insertions
            addIfNotNil: (self insertionOf: aString at: eachPoint isHorizontal: true);
            addIfNotNil: (self insertionOf: aString at: eachPoint isHorizontal: false)
        ].
    insertions removeAllSuchThat: [:each |
        self isInsertion: each invalidWith: aString asInteger
        ].
    ^insertions detectMax: [:each |
        (each accidentalPrimes size * 1) + (each numberOfOverlaps * 2)
        ]

insertionOf: aString at: aPoint isHorizontal: isHorizontal
    | point insertion |
    point := aPoint.
    (self canFitEndsAt: point length: aString size isHorizontal: isHorizontal)
        ifFalse: [^nil].
    (self isAlreadyThere: aString at: aPoint isHorizontal: isHorizontal)
        ifTrue: [^nil].
    insertion := Insertion at: point isHorizontal: isHorizontal.
    1 to: aString size do: [:eachIndex |
        | eachCharacter |
        eachCharacter := aString at: eachIndex.
        (self canDoInsertion: insertion of: eachCharacter at: point)
            ifTrue: [
                (self at: point) == eachCharacter
                    ifTrue: [insertion increaseOverlaps].
                point := point + (self offset: isHorizontal)
                ]
            ifFalse: [^nil]
        ].
    ^insertion

isInsertion: anInsertion invalidWith: aPrime
    | otherPrimes |
    otherPrimes := anInsertion accidentalPrimes.
    ^(primesUsed includesAny: otherPrimes)
        or: [(otherPrimes includes: aPrime)
        or: [otherPrimes copy removeDuplicates size < otherPrimes size]]

canDoInsertion: anInsertion of: aCharacter at: aPoint
    "Answer whether anInsertion of aCharacter is valid at aPoint. If so,
    also update anInsertion with any accidental insertions."

    | perpendicularSequence offset front back |
    (self at: aPoint) == aCharacter
        ifTrue: [^true].
    (self isFreeAt: aPoint)
        ifFalse: [^false].
    perpendicularSequence := OrderedCollection with: aCharacter.
    offset := self offset: anInsertion isHorizontal not.
    front := aPoint - offset.
    back := aPoint + offset.
    [self isFreeOrBorder: front] whileFalse: [
        perpendicularSequence addFirst: (self at: front).
        front := front - offset
        ].
    [self isFreeOrBorder: back] whileFalse: [
        perpendicularSequence addLast: (self at: back).
        back := back + offset
        ].
    ^perpendicularSequence size == 1
        or: [
            | string number |
            string := String withAll: perpendicularSequence.
            number := string asInteger.
            (string first ~~ $0 and: [number isPrime])
                ifTrue: [anInsertion addAccidentalPrime: number. true]
                ifFalse: [false]
            ]

doInsertion: anInsertion of: aPrime
    self
        insert: aPrime printString
        at: anInsertion point
        horizontalIf: anInsertion isHorizontal.
    primesUsed
        add: aPrime;
        addAll: anInsertion accidentalPrimes

growMatrixByOneUpTo: aDimension
    | smallMatrix rowOffset columnOffset |
    smallMatrix := matrix copy.
    matrix := Matrix
        rows: (self height + 2 min: aDimension y)
        columns: (self width + 2 min: aDimension x)
        element: Character space.
    rowOffset := (self height - smallMatrix numberOfRows) min: 1.
    columnOffset := (self width - smallMatrix numberOfColumns) min: 1.
    self copy: smallMatrix to: (1 + columnOffset) @ (1 + rowOffset)

copy: aMatrix to: aPoint
    matrix
        atRows: aPoint y
        to: aPoint y + aMatrix numberOfRows - 1
        columns: aPoint x
        to: aPoint x + aMatrix numberOfColumns - 1
        put: aMatrix

Collection
Oh, and I added one method to the instance side of Collection, just for convenience:
addIfNotNil: anElement
    anElement ifNotNil: [self add: anElement]

Running it
To run my code, all I need to do is select the following code in a workspace ("playground" in Pharo) or in any text pane, and "do it" from the context menu:
(Stuffer forDimensions: 80@60)
    stuffBox

The rest of the code is relatively boring.
As I said, room for improvement, but at 80x60, each run takes over 3 minutes on my machine. Clearly, performance hasn't been my concern, but there are a LOT of primes flying around. This sure has been an interesting challenge. :-)

Wow. That is a well thought out answer and excellent explanation. This is exactly the type of answer I was hoping for when I set the challenge. Your choice to only include and explain the key parts of your code is fine. The whole program you have linked to is quite large.

Amos, if you enjoy difficult challenges, you might find some I have posted earlier to be of interest: http://codegolf.stackexchange.com/users/31785/carpetpython?tab=questions

Many thanks, and I'll be sure to take a look at some of those other questions for the next rainy day. I'm not much for code golfing (I believe in practice it's more important to be able to write readable, maintainable code, though I marvel at stuff other people come up with on this site and appreciate succinct, elegant code), so when I come here I usually look for exactly this type of challenge.

Javascript, score 659
Almost certainly suboptimal.
lenof=function(a){return (""+a).length}
Array.prototype.peek=function(){return this[this.length-1]}
primes=[
11, 13, 17, 19, 23, 29, 31,
37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97,
101, 103, 107, 109, 113, 127,
131, 137, 139, 149, 151, 157,
163, 167, 173, 179, 181, 191,
193, 197, 199, 211, 223, 227,
229, 233, 239, 241, 251, 257,
263, 269, 271, 277, 281, 283,
293, 307, 311, 313, 317, 331,
337, 347, 349,401, 409, 419,
421, 431, 433, 439, 443, 449,
457, 461, 463, 467, 479, 487,
491, 499, 503, 509, 521, 523,
541, 547, 557, 563, 569, 571,
577, 587, 593, 599, 601, 607,
613, 617, 619, 631, 641, 643,
647, 653, 659, 661, 673, 677,
683, 691, 701, 709, 719, 727,
733, 739, 743, 751, 757, 761,
769, 773, 787, 797, 809, 811,
821, 823, 827, 829, 839, 853,
857, 859, 863, 877, 881, 883,
887, 907, 911, 919, 929, 937,
941, 947, 953, 967, 971, 977,
983, 991, 997,1009, 1013, 1019,
1021, 1031, 1033, 1039, 1049,
1051, 1061, 1063, 1069, 1087,
1091, 1093, 1097, 1103, 1109,
1117, 1123, 1129, 1151, 1153,
1163, 1171, 1181, 1187, 1193,
1201, 1213, 1217, 1223, 1229,
1231, 1237, 1249, 1259, 1277,
1279, 1283, 1289, 1291, 1297,
1301, 1303, 1307, 1319, 1321,
1327, 1361, 1367, 1373, 1381,
1399, 1409, 1423, 1427, 1429,
1433, 1439, 1447, 1451, 1453,
1459, 1471, 1481, 1483, 1487,
1489, 1493, 1499, 1511, 1523,
1531, 1543, 1549, 1553, 1559,
1567, 1571, 1579, 1583, 1597,
1601, 1607, 1609, 1613, 1619,
1621, 1627, 1637, 1657, 1663,
1667, 1669, 1693, 1697, 1699,
1709, 1721, 1723, 1733, 1741,
1747, 1753, 1759, 1777, 1783,
1787, 1789, 1801, 1811, 1823,
1831, 1847, 1861, 1867, 1871,
1873, 1877, 1879, 1889, 1901,
1907, 1913, 1931, 1933, 1949,
1951, 1973, 1979, 1987, 1993,
1997, 1999, 2003, 2011, 2017,
2027, 2029, 2039, 2053, 2063,
2069, 2081, 2083, 2087, 2089,
2099, 2111, 2113, 2129, 2131,
2137, 2141, 2143, 2153, 2161,
2179, 2203, 2207, 2213, 2221,
2237, 2239, 2243, 2251, 2267,
2269, 2273, 2281, 2287, 2293,
2297, 2309, 2311, 2333, 2339,
2341, 2347, 2351, 2357, 2371,
2377, 2381, 2383, 2389, 2393,
2399, 2411, 2417, 2423, 2437,
2441, 2447, 2459, 2467, 2473,
2477, 2503, 2521, 2531, 2539,
2543, 2549, 2551, 2557, 2579,
2591, 2593, 2609, 2617, 2621,
2633, 2647, 2657, 2659, 2663,
2671, 2677, 2683, 2687, 2689,
2693, 2699, 2707, 2711, 2713,
2719, 2729, 2731, 2741, 2749,
2753, 2767, 2777, 2789, 2791,
2797, 2801, 2803, 2819, 2833,
2837, 2843, 2851, 2857, 2861,
2879, 2887, 2897, 2903, 2909,
2917, 2927, 2939, 2953, 2957,
2963, 2969, 2971, 2999, 3001,
3011, 3019, 3023, 3037, 3041,
3049, 3061, 3067, 3079, 3083,
3089, 3109, 3119, 3121, 3137,
3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973
];
width=+prompt`Width`;
height=+prompt`Height`;
pre=document.createElement("pre");
lis=[];
q=0;
z:while(lis.length<height){
s=lis.length%2?"":"    ";
while(true){
v=primes[q++];
if((s+("   "+v).slice(-4)).length>width)break;
s=s+("   "+v).slice(-4);
if(q>=primes.length){lis.push(s);break z;}
if(s.length<width)s+="    ";
}
lis.push((s+" ".repeat(width)).substring(0,width));
}
document.body.appendChild(pre);
for(z of lis){
pre.innerHTML+=z+"\n";

}

Results for 30x30:
      11      13      17
  23      29      31      37
      43      47      53
  61      67      71      73
      83      89      97
 103     107     109     113
     131     137     139
 151     157     163     167
     179     181     191
 197     199     211     223
     229     233     239
 251     257     263     269
     277     281     283
 307     311     313     317
     337     347     349
 409     419     421     431
     439     443     449
 461     463     467     479
     491     499     503
 521     523     541     547
     563     569     571
 587     593     599     601
     613     617     619
 641     643     647     653
     661     673     677
 691     701     709     719
     733     739     743
 757     761     769     773
     797     809     811
 823     827     829     839

And for the 60x60 case:
      11      13      17      19      23      29      31      37      41      43
  53      59      61      67      71      73      79      83      89      97
     103     107     109     113     127     131     137     139     149     151
 163     167     173     179     181     191     193     197     199     211
     227     229     233     239     241     251     257     263     269     271
 281     283     293     307     311     313     317     331     337     347
     401     409     419     421     431     433     439     443     449     457
 463     467     479     487     491     499     503     509     521     523
     547     557     563     569     571     577     587     593     599     601
 613     617     619     631     641     643     647     653     659     661
     677     683     691     701     709     719     727     733     739     743
 757     761     769     773     787     797     809     811     821     823
     829     839     853     857     859     863     877     881     883     887
 911     919     929     937     941     947     953     967     971     977
     991     997    1009    1013    1019    1021    1031    1033    1039    1049
1061    1063    1069    1087    1091    1093    1097    1103    1109    1117
    1129    1151    1153    1163    1171    1181    1187    1193    1201    1213
1223    1229    1231    1237    1249    1259    1277    1279    1283    1289
    1297    1301    1303    1307    1319    1321    1327    1361    1367    1373
1399    1409    1423    1427    1429    1433    1439    1447    1451    1453
    1471    1481    1483    1487    1489    1493    1499    1511    1523    1531
1549    1553    1559    1567    1571    1579    1583    1597    1601    1607
    1613    1619    1621    1627    1637    1657    1663    1667    1669    1693
1699    1709    1721    1723    1733    1741    1747    1753    1759    1777
    1787    1789    1801    1811    1823    1831    1847    1861    1867    1871
1877    1879    1889    1901    1907    1913    1931    1933    1949    1951
    1979    1987    1993    1997    1999    2003    2011    2017    2027    2029
2053    2063    2069    2081    2083    2087    2089    2099    2111    2113
    2131    2137    2141    2143    2153    2161    2179    2203    2207    2213
2237    2239    2243    2251    2267    2269    2273    2281    2287    2293
    2309    2311    2333    2339    2341    2347    2351    2357    2371    2377
2383    2389    2393    2399    2411    2417    2423    2437    2441    2447
    2467    2473    2477    2503    2521    2531    2539    2543    2549    2551
2579    2591    2593    2609    2617    2621    2633    2647    2657    2659
    2671    2677    2683    2687    2689    2693    2699    2707    2711    2713
2729    2731    2741    2749    2753    2767    2777    2789    2791    2797
    2803    2819    2833    2837    2843    2851    2857    2861    2879    2887
2903    2909    2917    2927    2939    2953    2957    2963    2969    2971
    3001    3011    3019    3023    3037    3041    3049    3061    3067    3079
3089    3109    3119    3121    3137    3163    3167    3169    3181    3187
    3203    3209    3217    3221    3229    3251    3253    3257    3259    3271
3301    3307    3313    3319    3323    3329    3331    3343    3347    3359
    3371    3373    3389    3391    3407    3413    3433    3449    3457    3461
3467    3469    3491    3499    3511    3517    3527    3529    3533    3539
    3547    3557    3559    3571    3581    3583    3593    3607    3613    3617
3631    3637    3643    3659    3671    3673    3677    3691    3697    3701
    3719    3727    3733    3739    3761    3767    3769    3779    3793    3797
3821    3823    3833    3847    3851    3853    3863    3877    3881    3889
    3911    3917    3919    3923    3929    3931    3943    3947    3967    3989
4003    4007    4013    4019    4021    4027    4049    4051    4057    4073
    4091    4093    4099    4111    4127    4129    4133    4139    4153    4157
4177    4201    4211    4217    4219    4229    4231    4241    4243    4253
    4261    4271    4273    4283    4289    4297    4327    4337    4339    4349
4363    4373    4391    4397    4409    4421    4423    4441    4447    4451
    4463    4481    4483    4493    4507    4513    4517    4519    4523    4547
4561    4567    4583    4591    4597    4603    4621    4637    4639    4643
    4651    4657    4663    4673    4679    4691    4703    4721    4723    4729
4751    4759    4783    4787    4789    4793    4799    4801    4813    4817
    4861    4871    4877    4889    4903    4909    4919    4931    4933    4937
4951    4957    4967    4969    4973    4987    4993    4999    5003    5009