Lonely Numbers
题意翻译
### 题目大意
我们规定对于两个不同的数字 $a,b$ ,如果$\gcd(a,b),\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}$ 可以构成一个三角形,那么 $a,b$ 便是一组好朋友.
我们进一步规定,如果在一个集合中中,有一数字 $k$ 和这个集合中任意一个数字都不是朋友,那么数字 $k$ 就是一个孤独数字.
给定一个包含所有 $1$ 到 $n$ 整数的集合,求在该集合中有多少数字是孤独数字.
### 输入输出格式
第一行输入一个整数 $T$ 表示有 $T$ 组数据.
接下来一行 $T$ 个数字,其中第 $i$ 个数字为 $n_{i}$ ,表示你应解决当 $n=n_{i}$ 时的问题.
你应输出 $T$ 行,第 $i$ 行为当 $n=n_{i}$ 时孤独数字的数量.
### 样例解释
当 $n=1$ 时, $1$ 是集合中唯一的数字,因此它是孤独数字.
当 $n=5$ 时, 孤独数字为$1,3,5$.
当 $n=10$ 时, 孤独数字为$1,5,7$.
题目描述
In number world, two different numbers are friends if they have a lot in common, but also each one has unique perks.
More precisely, two different numbers $ a $ and $ b $ are friends if $ gcd(a,b) $ , $ \frac{a}{gcd(a,b)} $ , $ \frac{b}{gcd(a,b)} $ can form sides of a triangle.
Three numbers $ a $ , $ b $ and $ c $ can form sides of a triangle if $ a + b > c $ , $ b + c > a $ and $ c + a > b $ .
In a group of numbers, a number is lonely if it doesn't have any friends in that group.
Given a group of numbers containing all numbers from $ 1, 2, 3, ..., n $ , how many numbers in that group are lonely?
输入输出格式
输入格式
The first line contains a single integer $ t $ $ (1 \leq t \leq 10^6) $ - number of test cases.
On next line there are $ t $ numbers, $ n_i $ $ (1 \leq n_i \leq 10^6) $ - meaning that in case $ i $ you should solve for numbers $ 1, 2, 3, ..., n_i $ .
输出格式
For each test case, print the answer on separate lines: number of lonely numbers in group $ 1, 2, 3, ..., n_i $ .
输入输出样例
输入样例 #1
3
1 5 10
输出样例 #1
1
3
3
说明
For first test case, $ 1 $ is the only number and therefore lonely.
For second test case where $ n=5 $ , numbers $ 1 $ , $ 3 $ and $ 5 $ are lonely.
For third test case where $ n=10 $ , numbers $ 1 $ , $ 5 $ and $ 7 $ are lonely.