5. In the cells of an $80 \times 80$ table, pairwise distinct natural numbers are placed. Each of them is either a prime number or a product of two prime numbers (possibly the same). 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: 4266.

Solution. We will say that a composite number $a$ serves a prime number $p$ if $a$ and $p$ are not coprime (i.e., $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 two distinct prime divisors, it serves no more than two prime numbers. Thus, if the table contains $n$ composite numbers, then the number of primes does not exceed $2n$. Therefore, the total number of numbers in the table does not exceed $3n$. Then

$$
3n \geqslant 80^{2} \Longrightarrow n \geqslant \frac{80^{2}}{3}=2133 \frac{1}{3} \Longrightarrow n \geqslant 2134 \Longrightarrow 80^{2}-n \leqslant 80^{2}-2134=4266
$$

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

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

1) The first 52 positions are filled with different prime numbers $p_{1}, p_{2}, \ldots, p_{52}$. These numbers must be new, i.e., not used before in the table.
2) In the next 26 cells, we place the numbers $p_{1} p_{2}, p_{3} p_{4}, \ldots, p_{51} p_{52}$.
3) The last two positions are left unfilled.

We apply this algorithm sequentially to the rows $1,2, \ldots, 80$, and then to the last two columns. Thus, we will place $80 \cdot 52 + 2 \cdot 52 = 4264$ prime numbers. It remains to fill the $2 \times 2$ square in the bottom right corner. In it, on one diagonal, we will place a pair of new prime numbers, and on the other diagonal - their squares. In the end, we will place 4266 different prime numbers.