codeforces-scrape

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

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