등차수열에 관한 디리클레의 정리

등차수열에 관한 디리클레의 정리는 서로소인 두 양의 정수 a와 b가 있을 때, 등차수열 t(n) = a*n + b (n ≥ 0)은 무한히 많은 소수를 포함한다는 내용이다. 소수는 2보다 큰 양의 정수로, 약수가 1과 자기자신 밖에 없는 수이다.

예를 들어, a=4, b=3인 경우 등차수열은 다음과 같다.

3, 7, 11, 15, 19, 23, 27, 31, 35, ...,

여기서 이 등차수열의 첫 부분에 많은 소수가 있음을 눈으로 볼 수 있다.

a > 0과 b ≥ 0, 그리고 U ≥ L ≥ 0이 주어졌을 때, t(n) = a*n+b에 소수가 몇 개 있는지 구하는 프로그램을 작성하시오. (L ≤ n ≤ U)

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 a, b, L, U를 포함하며, 한 줄로 이루어져 있다. a*U+b ≤ 1012이고, U - L ≤ 106이다. 마지막 줄에는 0이 주어진다.

각 테스트 케이스에 대해서, 테스트 케이스 번호와 L ≤ n ≤ U에서 t(n)이 소수인 것의 개수를 출력한다.