시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 17 7 7 43.750%

문제

정수론 중간고사를 마치고 집으로 돌아온 상근이는 패닉에 빠졌다. 유일하게 공부를 하지 않은 것이 오일러 피 함수(Euler's totient function, \(\varphi \))였는데, 그 함수에 관한 문제만 나왔기 때문이다. 상근이는 너무 억울했고, 직접 Totient 함수를 만들기로 했다.

정수론에서 양의 정수의 소인수는 그 정수를 나머지 없이 나눌 수 있는 소수이다. 상근이는 n ≥ 2에서 함수 F(n)을 곱이 n이 되는 감소하지 않는 소수의 리스트로 정의했다. 예를 들어, F(8) = «2,2,2», F(60) = «2,2,3,5», F(71) = «71» 이다. O(n)은 F(n)의 길이이다. 예를 들어, O(8) = 3, O(60) = 4, O(71) = 1 이 된다. 마지막으로, 양의 정수에 대해서 \(p(n)\)을 다음과 같이 정의했다.

\(p(n) = \begin{cases} 0 & \text{if } n = 1 \\ -1 & \text{if } n \text{ is a prime number} \\ O(n) & \text {otherwise} \end{cases}\)

아래 표에는 \(p(n)\)의 첫 20개 값이 나와있다.

a ≤ b를 만족하는 두 양의 정수 a와 b에 대해서, 상근이는 자신의 Totient 함수인 \(\varphi(a,b)\)를 다음과 같이 정의했다.

\(\varphi (a,b)= ( \sum _{ k=a }^{ b }{ p(k) }  )  - (b-a+1)\)

예를 들어, \(\varphi(1,4) = -4\), \(\varphi(16,16) = 3\), \(\varphi(8,12) = 4\) 이다.

구간 [L, U]가 주어졌을 때, 가장 큰 값을 갖는 \(\varphi\)를 찾는 프로그램을 작성하시오.

즉, L ≤ U를 만족하는 두 양의 정수 L과 U가 주어졌을 때, 가장 큰 \(\varphi(a,b)\) (L ≤ a ≤ b ≤ U) 를 찾는 프로그램을 작성하시오. 예를 들어, 구간 [1,20]에서 가장 큰 \(\varphi\)는 7이다. (\(\varphi(8,16)\))

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L과 U가 주어진다. (1 ≤ L ≤ U < 1,000,000)

입력의 마지막 줄에는 -1이 두 개 주어진다.

출력

각 테스트 케이스마다 주어진 구간 [L, U]에서 찾을 수 있는 가장 큰 \(\varphi\) 값을 출력한다.

예제 입력

1 5
1 20
10 20
900000 901000
-1 -1

예제 출력

1. 1
2. 7
3. 5
4. 2551

힌트