Будем го­во­рить, что со­став­ное число а об­слу­жи­ва­ет про­стое число p, если числа a и p не вза­им­но про­сты (то есть a де­лит­ся на p). Для каж­до­го про­сто­го числа в таб­ли­це есть об­слу­жи­ва­ю­щее его со­став­ное. По­сколь­ку каж­дое со­став­ное число имеет не более двух раз­лич­ных про­стых де­ли­те­лей, оно об­слу­жи­ва­ет не более двух про­стых чисел. Таким об­ра­зом, если таб­ли­ца со­дер­жит n со­став­ных чисел, то про­стых  — не более 2n. Сле­до­ва­тель­но, общее ко­ли­че­ство чисел в таб­ли­це не пре­вос­хо­дит 3n. Тогда

Зна­чит, ко­ли­че­ство про­стых чисел в таб­ли­це не пре­вос­хо­дит 4266.

По­ка­жем те­перь, как можно раз­ме­стить в таб­ли­це 4266 про­стых чисел. Вос­поль­зу­ем­ся сле­ду­ю­щим ал­го­рит­мом за­пол­не­ния строк и столб­цов.

1)  Пер­вые 52 по­зи­ции за­пол­ня­ем раз­лич­ны­ми про­сты­ми чис­ла­ми p₁, p₂, ..., p₅₂. Эти числа долж­ны быть но­вы­ми, то есть не ис­поль­зо­вав­ши­ми­ся ранее в таб­ли­це.

2)  В сле­ду­ю­щих 26 клет­ках раз­ме­ща­ем числа p₁p₂, p₃p₄, ..., p₅₁p₅₂.

3)  По­след­ние две по­зи­ции остав­ля­ем не­за­пол­нен­ны­ми.

При­ме­ним этот ал­го­ритм по­сле­до­ва­тель­но сна­ча­ла к стро­кам 1, 2, ..., 80, а затем к двум по­след­ним столб­цам. Тем самым мы рас­ста­вим

про­стых числа. Оста­лось за­пол­нить клет­ки квад­ра­та 2 × 2 из пра­во­го ниж­не­го угла. В нем на одной диа­го­на­ли мы по­ста­вим пару новых про­стых чисел, а на дру­гой  — их квад­ра­ты. В итоге мы раз­ме­стим 4266 раз­лич­ных про­стых чисел.

Ответ: 4266.