되 나눔수

문제 설명

임의의 정수 n이 있을때, n의 약수의 개수로 n을 나눌 수 있을 경우 이를 되 나눔수 라고 한다

예를 들어 1(1개), 12(6개), 9(3개)의 경우 되 나눔이 가능하지만 7(2개), 16(5개)의 경우 되 나눔이 되지 않는다

숫자 a, b (1≤a≤b≤1000000)(b-a≤1000)이 입력되었을 경우, a,b를 포함하여 a부터 b 사이에 있는 수 중 되 나눔 수의 개수를 구하는 프로그램을 작성하고자 한다

입력

첫째 줄에 검사하고자 하는 총 경우의 수 T (1≤T≤50)가 주어진다

이어지는 T 줄 각각엔 두 정수 a, b가 하나의 공백으로 구분되어 주어진다

출력

검사하는 각 경우에 대해 a부터 b 사이에 있는 수 중 되 나눔 수의 개수를 출력하라

실행 예시

입력

6
1 2
1 200
904 1217
31924 32430
67890 68888
891256 892256

출력

2
25
22
31
50
44

문제 풀이

#include<iostream>

using namespace std;

int cnt, first, second; // 테스트 케이스 개수, 첫 번째 입력값, 두 번째 입력값 설정
int check, divisior; // 약수의 개수, 되 나눔수 개수 설정

int main() {

	cin >> cnt;
	for (int k = 0; k < cnt; k++) {
		cin >> first >> second; // 입력
		divisior = 0; // 되 나눔수 개수 초기화
		for (int i = first; i <= second; i++) {
			check = 0; // 약수 개수 초기화
			for (int j = 1; j * j <= i; j++) { // j의 제곱 수 보다 작으면 반복문 중지
				if (i % j == 0) { // j가 i의 약수 일 때,
					if (j * j == i) check++; // i가 j의 제곱 수 이면 약수의 개수 1 증가
					if (j * j < i) check += 2; // i가 j의 제곱 수 보다 크면 약수의 개수 2개 증가 -> j와 짝을 이루는 다른 약수가 존재하므로 2개를 증가
				}
			} // 약수의 개수 확인
			if (i % check == 0) divisior++; // 약수의 개수로 i가 나누어지면 되 나눔수 개수 1 증가 
		} // a~b 까지의 되 나눔수 개수 체크
		cout << divisior << "\\n";
	} // 검사하고자 하는 테스트 케이스만큼 반복
	return 0;
}