5. In the cells of a $75 \times 75$ table, pairwise distinct natural numbers are placed. Each of them has no more than three distinct prime divisors. It is known that for any number $a$ in the table, there is a number $b$ in the same row or column such that $a$ and $b$ are not coprime. What is the maximum number of prime numbers that can be in the table?
Answer: 4218.

Solution. We will say that a composite number $a$ serves a prime number $p$ if the numbers $a$ and $p$ are not coprime (that is, $a$ is divisible by $p$). For each prime number in the table, there is a composite number that serves it. Since each composite number has no more than three distinct prime divisors, it serves no more than three prime numbers. Thus, if the table contains $n$ composite numbers, then the number of primes does not exceed $3n$. Therefore, the total number of numbers in the table does not exceed $4n$. Then

$$
4n \geqslant 75^{2} \Longrightarrow n \geqslant \frac{75^{2}}{4}=1406 \frac{1}{4} \Longrightarrow n \geqslant 1407 \Longrightarrow 75^{2}-n \leqslant 75^{2}-1407=4218
$$

Thus, the number of prime numbers in the table does not exceed 4218.

Now let's show how 4218 prime numbers can be placed in the table. We will use the following algorithm for filling rows and columns.

1) The first 54 positions are filled with different prime numbers $p_{1}, p_{2}, \ldots, p_{54}$. These numbers must be new, that is, not used before in the table.
2) In the next 18 cells, we place the numbers $p_{1} p_{2} p_{3}, p_{4} p_{5} p_{6}, \ldots, p_{52} p_{53} p_{54}$.
3) The last three positions are left unfilled.

We apply this algorithm sequentially to the rows $1,2, \ldots, 75$, and then to the last three columns. Thus, we will place $75 \cdot 54 + 3 \cdot 54 = 4212$ prime numbers. It remains to fill the cells of the $3 \times 3$ square in the lower right corner. We choose new prime numbers $q_{1}, \ldots, q_{6}$ and place them as follows:

$$
\left(\begin{array}{ccc}
q_{1} q_{2} & q_{3} q_{4} & q_{5} q_{6} \\
q_{1} & q_{3} & q_{5} \\
q_{2} & q_{4} & q_{6}
\end{array}\right)
$$

In the end, we will place 4218 different prime numbers.