문제1062--소수 구하기 III

1062: 소수 구하기 III

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 1056  통과: 390
[제출] [채점기록] [묻고답하기]

문제 설명

소수란 1과 자기 자신을 제외한 그 어떤 수로도 나누어 떨어지지 않는 수를 말한다.

예를 들어 2, 3, 5, 7 등은 1과 자기 자신을 제외한 어떤 수로도 나누어 떨어지지 않으므로 소수지만 4는 1과 자기 자신 이외에도 2로 나누어 떨어지기 때문에 소수가 아니다.

두 수를 a, b를 입력받았을 때 a부터 b까지 있는 수중에 소수가 몇 개인지 찾는 프로그램을 작성하라. (a, b 소수일 경우 a, b 자기 자신도 포함한다)

 

입력 설명

맨 처음 테스트 케이스의 개수 $T(1 \leq T \leq 20)$를 입력받는다. 그 뒤에 T의 개수만큼 $A, B(0 \leq A < B \leq 100000)$를 입력받는다.

출력 설명

각 테스트 케이스마다 A, B 사이에 존재하는 소수의 개수를 출력한다.

입력 예시 Copy

3
2 10
50 100
100 1000

출력 예시 Copy

4
10
143

출처/분류