Клетчатые задачи и комбинаторные подсчёты на СПБГУ

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

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

Первые позиции заполняем различными простыми числами Эти числа должны быть новыми, то есть не использовавшимися ранее в таблице.

В следующих клетках размещаем числа

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

Применим этот алгоритм последовательно сначала к строкам а затем к двум последним столбцам. Тем самым мы расставим простых числа. Осталось заполнить клетки квадрата из правого нижнего угла. В нем на одной диагонали мы поставим пару новых простых чисел, а на другой — их квадраты. В итоге мы разместим различных простых чисел.