2091E.md (1811B)
1 Source: https://codeforces.com/problemset/problem/2091/E 2 3 E. Interesting Ratio 4 5 time limit per test 6 7 2 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 Recently, Misha at the IT Campus "NEIMARK" camp learned a new topic — the Euclidean algorithm. 22 23 He was somewhat surprised when he realized that $a \cdot b = lcm(a, b) \cdot gcd(a, b)$, where $gcd(a, b)$ — is [the greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of the numbers $a$ and $b$ and $lcm(a, b)$ — is [the least common multiple (LCM)](https://en.wikipedia.org/wiki/Least_common_multiple). Misha thought that since the product of LCM and GCD exists, it might be interesting to consider their quotient: $F(a,b)=\frac{lcm(a, b)}{gcd(a, b)}$. 24 25 For example, he took $a = 2$ and $b = 4$, computed $F(2, 4) = \frac{4}{2} = 2$ and obtained a prime number (a number is prime if it has exactly two divisors)! Now he considers $F(a, b)$ to be an interesting ratio if $a \lt b$ and $F(a, b)$ is a prime number. 26 27 Since Misha has just started studying number theory, he needs your help to calculate — how many different pairs of numbers $a$ and $b$ are there such that $F(a, b)$ is an interesting ratio and $1 \leq a \lt b \leq n$? 28 29 Input 30 31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^3$). The description of the test cases follows. 32 33 A single line of each test case contains a single integer $n$ ($2 \leq n \leq 10^7$). 34 35 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^7$. 36 37 Output 38 39 For each test case, output the number of interesting ratios $F(a, b)$ for pairs satisfying $1 \leq a \lt b \leq n$. 40 41 Example 42 43 Input 44 45 ``` 46 4 47 48 5 49 50 10 51 52 34 53 54 10007 55 ``` 56 57 Output 58 59 ``` 60 4 61 11 62 49 63 24317 64 ```