CF1423K Lonely Numbers

在数字世界中，如果两个不同的数字有很多共同点，但每个数字又各有独特之处，那么它们就是朋友。 更准确地说，两个不同的数字 $a$ 和 $b$ 是朋友，当且仅当 $gcd(a,b)$、$\frac{a}{gcd(a,b)}$、$\frac{b}{gcd(a,b)}$ 可以作为三角形的三条边。 三个数 $a$、$b$ 和 $c$ 能作为三角形的三条边，当且仅当 $a + b > c$，$b + c > a$ 且 $c + a > b$。 在一组数字中，如果某个数字在该组中没有任何朋友，则称其为孤独数字。 给定一个包含 $1, 2, 3, ..., n$ 的数字集合，问在这个集合中有多少个孤独数字？

第一行包含一个整数 $t$（$1 \leq t \leq 10^6$），表示测试用例的数量。 接下来一行包含 $t$ 个数字 $n_i$（$1 \leq n_i \leq 10^6$），表示第 $i$ 个测试用例需要对 $1, 2, 3, ..., n_i$ 这组数字进行求解。

对于每个测试用例，输出一行，表示在 $1, 2, 3, ..., n_i$ 这组数字中孤独数字的个数。

对于第一个测试用例，只有 $1$ 这一个数字，因此它是孤独的。 对于第二个测试用例，$n=5$，数字 $1$、$3$ 和 $5$ 是孤独的。 对于第三个测试用例，$n=10$，数字 $1$、$5$ 和 $7$ 是孤独的。 由 ChatGPT 4.1 翻译