Problem 1840

Answer: $617$.

To begin with, let's give an example of $616$ numbers from $1$ to $1000$, among which there are no prime squares and no two of which are divisible by the square of a prime. To do this, take $8$ numbers of the form $2p^2$ not exceeding $500$, where $p$ is a prime number:
$$2 \cdot 2^2,\ 2 \cdot 3^2,\ 2 \cdot 5^2,\ 2 \cdot 7^2,\ 2 \cdot 11^2,\ 2 \cdot 13^2,\ 2 \cdot 17^2,\ 2 \cdot 19^2$$
and also all natural numbers from $1$ to $1000$, free from squares (that is, not divisible by the square of any prime number). There are only $608$ of them. To make sure of this, use the inclusion-exclusion formula:
$$1000 - \sum_{1 \le i \le 11} \left\lfloor \frac{1000}{p_i^2} \right\rfloor + \sum_{1 \le i < j \le 11} \left\lfloor \frac{1000}{p_i^2 p_j^2} \right\rfloor - \sum_{1 \le i < j < k \le 11} \left\lfloor \frac{1000}{p_i^2 p_j^2 p_k^2} \right\rfloor,$$
where $p_1 = 2$, $p_2 = 3$, $p_3 = 5$, $p_4 = 7$, $p_5 = 11$, $p_6 = 13$, $p_7 = 17$, $p_8 = 19$, $p_9 = 23$, $p_{10} = 29$, $p_{11} = 31$. We get
$$\begin{aligned} 1000 & - (250 + 111 + 40 + 20 + 8 + 5 + 3 + 2 + 1 + 1 + 1) \\ & + \left( \left\lfloor \frac{1000}{2^2 3^2} \right\rfloor + \left\lfloor \frac{1000}{2^2 5^2} \right\rfloor + \left\lfloor \frac{1000}{2^2 7^2} \right\rfloor + \left\lfloor \frac{1000}{2^2 11^2} \right\rfloor + \left\lfloor \frac{1000}{2^2 13^2} \right\rfloor + \left\lfloor \frac{1000}{3^2 5^2} \right\rfloor + \left\lfloor \frac{1000}{3^2 7^2} \right\rfloor \right) \\ & - \left\lfloor \frac{1000}{2^2 3^2 5^2} \right\rfloor = 1000 - 442 + (27 + 10 + 5 + 2 + 1 + 4 + 2) - 1 = 558 + 51 - 1 = 608. \end{aligned}$$
Now let's say there are $617$ numbers from $1$ to $1000$, among which there are no squares of prime numbers. Let us show that there are two of them that are divisible by the square of the same prime. Indeed, since there are only $608$ natural numbers not exceeding $1000$ and free from squares, then at least nine of these numbers are divisible by squares of prime numbers. Let us denote these numbers by $a_1, a_2, \dots, a_9$, and for each $1 \le i \le 9$ let $q_i^2$ be the square of a prime dividing $a_i$. If all $q_i^2$ are different, then some of them, say $q_k^2$, is not less than $23^2 = 529$. But since $a_k \ne q_k^2$, then $a_k \ge 2q_k^2 = 1048$. Contradiction. Therefore, there are two numbers divisible by the square of the same prime.