MMFMOB2 - Möbius function zero distribution
In number theory and combinatorics Möbius function μ(n) for integer n > 0 is defined as follows:
μ(1) = 1
μ(n) = (-1)k if n is the product of k (k > 0) distinct primes
μ(n) = 0 otherwise.
Let's define integer n > 0 as nfr point of Möbius function if μ(n) = 0. Given closed interval [a, b] compute number of nfr points from this interval.
Input
Each line of input contains two space separated random integer numbers a and b (1 ≤ a ≤ b ≤ 100 000 000). Input terminates with two space separated 0 (zero). There will be one input file.
Output
For each pair print required value on new line.
Example
Input: 1 1 2 4 3 7 4 10 5 9 6 10 0 0 Output: 0 1 1 3 2 2
Added by: | julkas |
Date: | 2018-05-16 |
Time limit: | 60s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |