E - Divide Both 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500 点

問題文

整数 L,R\ (L \le R) が与えられるので、以下の条件を全て満たす整数組 (x,y) の数を求めてください。

  • L \le x,y \le R
  • g を x,y の最大公約数とすると、以下が成立する。
    • g \neq 1 かつ \frac{x}{g} \neq 1 かつ \frac{y}{g} \neq 1

制約

  • 入力は全て整数
  • 1 \le L \le R \le 10^6

入力

入力は以下の形式で標準入力から与えられる。

L R

出力

答えを整数として出力せよ。

入力例 1

3 7

出力例 1

2

いくつかの整数組を例として示します。

  • (x,y)=(4,6) は条件を満たします。
  • (x,y)=(7,5) は g=1 となり、条件に違反します。
  • (x,y)=(6,3) は \frac{y}{g}=1 となり、条件に違反します。

条件を満たすのは (x,y)=(4,6),(6,4) の 2 組です。

入力例 2

4 10

出力例 2

12

入力例 3

1 1000000

出力例 3

392047955148

Score : 500 points

Problem Statement

Given integers L and L,R\ (L \le R), find the number of pairs (x,y) of integers satisfying all of the conditions below:

  • L \le x,y \le R
  • Let g be the greatest common divisor of x and y. Then, the following holds.
    • g \neq 1, \frac{x}{g} \neq 1, and \frac{y}{g} \neq 1.

Constraints

  • All values in input are integers.
  • 1 \le L \le R \le 10^6

Input

Input is given from Standard Input in the following format:

L R

Output

Print the answer as an integer.

Sample Input 1

3 7

Sample Output 1

2

Let us take some number of pairs of integers, for example.

  • (x,y)=(4,6) satisfies the conditions.
  • (x,y)=(7,5) has g=1 and thus violates the condition.
  • (x,y)=(6,3) has \frac{y}{g}=1 and thus violates the condition.

There are two pairs satisfying the conditions: (x,y)=(4,6),(6,4).

Sample Input 2

4 10

Sample Output 2

12

Sample Input 3

1 1000000

Sample Output 3

392047955148