1423K.md (1421B)
1 Source: https://codeforces.com/problemset/problem/1423/K 2 3 K. Lonely Numbers 4 5 time limit per test 6 7 1.5 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 In number world, two different numbers are friends if they have a lot in common, but also each one has unique perks. 22 23 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. 24 25 Three numbers $a$, $b$ and $c$ can form sides of a triangle if $a + b \gt c$, $b + c \gt a$ and $c + a \gt b$. 26 27 In a group of numbers, a number is lonely if it doesn't have any friends in that group. 28 29 Given a group of numbers containing all numbers from $1, 2, 3, ..., n$, how many numbers in that group are lonely? 30 31 Input 32 33 The first line contains a single integer $t$ $(1 \leq t \leq 10^6)$ - number of test cases. 34 35 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$. 36 37 Output 38 39 For each test case, print the answer on separate lines: number of lonely numbers in group $1, 2, 3, ..., n_i$. 40 41 Example 42 43 Input 44 45 ``` 46 3 47 1 5 10 48 ``` 49 50 Output 51 52 ``` 53 1 54 3 55 3 56 ``` 57 58 Note 59 60 For first test case, $1$ is the only number and therefore lonely. 61 62 For second test case where $n=5$, numbers $1$, $3$ and $5$ are lonely. 63 64 For third test case where $n=10$, numbers $1$, $5$ and $7$ are lonely.