언더프라임
면접 대비시간 제한2초메모리 제한128 MB
주어진 구간의 정수들 중 소인수(중복 포함) 개수가 소수인 언더프라임의 개수를 구합니다.
문제
자연수 X를 소인수분해하면, 곱해서 X가 되는 소수들의 목록을 얻을 수 있다. 예를 들어 12는 2 × 2 × 3으로 분해되므로 목록의 길이는 3이다. 1은 소수가 아니다.
어떤 수 X를 소인수분해했을 때 얻는 소수 목록의 길이가 소수이면, X를 언더프라임이라고 한다. 12는 목록의 길이가 3이고 3은 소수이므로 언더프라임이다.
두 정수 A와 B가 주어진다. A 이상 B 이하인 정수 중 언더프라임인 수의 개수를 구하라.
입력
첫째 줄에 두 정수 A와 B가 주어진다.
출력
첫째 줄에 A 이상 B 이하인 언더프라임의 개수를 출력한다.
제한
- 2 ≤ A ≤ B ≤ 100,000