AlgoSpot) PASS486

문제 : https://algospot.com/judge/problem/read/PASS486

주어진 범위내에서 정해진 약수의 갯수를 가지는 수를 찾는 문제입니다.

이를 해결하기위해서 주어진 범위내에서 수의 약수를 배열에 미리 저장해두고 찾는 방식을 사용했습니다.

가장작은수인 2부터 10,000,000까지 차례대로 약수의 갯수를 미리 구해서 문제를 해결했습니다.

이를 위해 에라토스테네스의 체를 이용해서 소인수분해한 수 중 최소의 수를 찾은후 그것을이용해서 각 수의 약수의 갯수를 구했습니다.

#include <iostream>
#include <math.h>

using namespace std;

const int MAX = 10000000;

int MinPrime[MAX + 1]; // 최소 소수

int MinPrimeNum[MAX + 1]; // 최소 소수가 몇승인지

int Factor[MAX + 1]; // 인자의 갯수

void Erastothenes() {
	MinPrime[0] = MinPrime[1] = -1;

	for (int i = 2; i <= MAX; ++i) MinPrime[i] = i;

	int sqrtn = int(sqrt(MAX));

	for (int i = 2; i <= sqrtn; ++i) {
		if (MinPrime[i] == i) {
			for (int j = i*i; j <= MAX; j += i) if(MinPrime[j] == j) MinPrime[j] = i;
		}
	}

	return;
}

void Find_Factor() {
	Factor[0] = Factor[1] = 1;

	for (int num = 2; num <= MAX; ++num) {
		if (MinPrime[num] == num) {
			Factor[num] = 2;
			MinPrimeNum[num] = 1;
		}
		else {
			int LowerNum = num / MinPrime[num];

			if (MinPrime[LowerNum] != MinPrime[num]) MinPrimeNum[num] = 1;
			else MinPrimeNum[num] = MinPrimeNum[LowerNum] + 1;

			Factor[num] = (Factor[LowerNum] / MinPrimeNum[num]) * (MinPrimeNum[num] + 1);
		}
	}
	return;
}

int main() {
	std::ios::sync_with_stdio(false);

	int C;
	int n, lo, hi;
	cin >> C;

	Erastothenes();
	Find_Factor();
	while (C--) {
		cin >> n >> lo >> hi;

		int answer = 0;

		for (int i = lo; i <= hi; ++i) 
			if (Factor[i] == n) ++answer;
		
		cout << answer << endl;
	}
	return 0;
}