codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```