Packing the Primes

Question

Here is a 5x4 rectangular wordsearch (area 20) containing the primes between 1 and 100,
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}
(numbers in any direction or diagonal/backwards, overlaps permitted (17 = 7,17,71))

15414
29763
38310
05100

It has a score of "4" because we were able to pack 4 unused zeros in there.

We can't make a 3x3 wordsearch as there are too many digits due to the '11';
in theory, the highest score we can get is "2" with a 3x4 wordsearch (area 12):

112
345
678
900
But this is missing primes like "23", so is invalid.

Without using a computer:
What is the minimum possible area for a valid rectangular wordsearch?
For a wordsearch with that area, what is the highest possible score you can find?
Provide an example.

Proof of optimality would be a bonus, by hand (preferred) or computer (acceptable), but I don't know if a proof beyond brute force exists, so am less concerned with that, although it would be interesting.

Answer 1

    258
    393
    174
    610
 

Proof of optimality:

Note that there is only one redundant digit. We'll show by contradiction that there is no arrangement without redundant digits. Otherwise, since 2,5,7,8 all have to pair with 3 and 9, 3 and 9 must be sandwiched between the 4 others. But 1 also has to pair with 3 and 9 and with itself which at this point is impossible with only two 1s.