2125C.md (1475B)
1 Source: https://codeforces.com/problemset/problem/2125/C 2 3 C. Count Good Numbers 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 A prime number is a positive integer that has exactly two divisors: $1$ and itself. The first several prime numbers are $2, 3, 5, 7, 11, \dots$. 22 23 Prime factorization of a positive integer is representing it as a product of prime numbers. For example: 24 25 * the prime factorization of $111$ is $3 \cdot 37$; 26 * the prime factorization of $43$ is $43$; 27 * the prime factorization of $12$ is $2 \cdot 2 \cdot 3$. 28 29 For every positive integer, its prime factorization is unique (if you don't consider the order of primes in the product). 30 31 We call a positive integer good if all primes in its factorization consist of at least two digits. For example: 32 33 * $343 = 7 \cdot 7 \cdot 7$ is not good; 34 * $111 = 3 \cdot 37$ is not good; 35 * $1111 = 11 \cdot 101$ is good; 36 * $43 = 43$ is good. 37 38 You have to calculate the number of good integers from $l$ to $r$ (endpoints included). 39 40 Input 41 42 The first line contains one integer $t$ ($1 \le t \le 10^3$) — the number of test cases. 43 44 Each test case consists of one line containing two integers $l$ and $r$ ($2 \le l \le r \le 10^{18}$). 45 46 Output 47 48 For each test case, print one integer — the number of good integers from $l$ to $r$. 49 50 Example 51 52 Input 53 54 ``` 55 4 56 57 2 100 58 59 2 1000 60 61 13 37 62 63 2 1000000000000000000 64 ``` 65 66 Output 67 68 ``` 69 21 70 227 71 7 72 228571428571428570 73 ```