Description

Nikolay and Asya investigate integers together in their spare time. Nikolay thinks an integer is interesting if it is a PRime number. However, Asya thinks an integer is interesting if the amount of its positive divisors is a prime number (e.g., number 1 has one divisor and number 10 has four divisors).

Nikolay and Asya are happy when their tastes about some integer are common. On the other hand, they are really upset when their tastes differ. They call an integer satisfying if they both consider or do not consider this integer to be interesting. Nikolay and Asya are going to investigate numbers from segment [L, R] this weekend. So they ask you to calculate the number of satisfying integers from this segment.

Input

In the only line there are two integers L and R (2≤L≤R≤1012$2/le L /le R /le 10^{12}$).

Output

In the only line output one integer — the number of satisfying integers from segment [L, R].

題意

Nikolay 認為一個數(shù)是有趣的，若這個數(shù)是素數(shù)；Asya 認為一個數(shù)是有趣的，當一個數(shù)的約數(shù)個數(shù)為 k ，且 k 是一個素數(shù)。

問在區(qū)間 [L,R]$[L, R]$ 中，兩人同時覺得有趣或同時覺得不有趣的數(shù)的個數(shù)。

分析

首先，當一個數(shù)是素數(shù)的時候，這個數(shù)的約數(shù)個數(shù)為 2 （1 和自身），是素數(shù)；即兩人必然同時認為一個素數(shù)是有趣的。

之后，考慮合數(shù)的情況。一個數(shù)約數(shù)的個數(shù)可以通過公式快速求得（套質(zhì)因數(shù)分解的板）： n→divisorNum=ab11×ab22×…×abtottot=(b1+1)×(b2+1)×...×(btot+1) $$/begin{align}n&=a_1^{b_1}×a_2^{b_2}×…×a_{tot}^{b_{tot}}///rightarrow divisorNum &= (b_1+1)/times(b_2+1)/times.../times(b_{tot}+1)/end{align}$$ 很容易看到，當一個合數(shù)的因子數(shù) >=2 時，這個數(shù)的約數(shù)個數(shù)必然是一個合數(shù)，則兩人同時認為這個數(shù)不有趣。

因此，只需要判斷一個素數(shù)的任意冪次，當 n=ab$n=a^b$ ，且 b+1 是一個素數(shù)的時候，兩人的判斷是不同的，將這部分數(shù)去除即可得到正確答案。

故預處理出 [1,106]$[1, 10^6]$ 區(qū)間中的素數(shù)，并以其為底，不斷獲取不同冪次的值，同時判斷 b+1 是否為素數(shù)。

HINT：由于最大右區(qū)間為 1012$10^{12}$ ，任意大于 106$10^6$ 的數(shù)的平方即大于 1012$10^{12}$ ，故不需要打更大的素數(shù)表。

代碼