[C++] 알고스팟/에라토스테네스의 체 - 비밀번호486

문제 링크

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

algospot.com :: PASS486

 

약수 n개를 가지고있는 숫자를 범위 low부터 high까지의 숫자들 중에서 찾아내는 문제입니다.

정수 x의 약수의 개수는 x 이전의 모든 값에 대한 약수의 개수와 가장 작은 소인수 값을 알고있으면 찾을 수 있습니다.

 

 

예를 들어 12의 약수의 개수를 알고싶고 1부터 11까지의 약수의 개수와 12를 포함한 모든 값들의 가장 작은 소인수를 알고 있습니다.

그럼 12를 12의 가장 작은 소인수인 2로 나누면 6이 됩니다.

12를 n, 6을 p라고 하고

 

n과 p의 가장 작은 소인수는 2로 같습니다.

이렇게 n과 p의 가장 작은 소인수가 같은 경우 p의 가장 작은 소인수의 개수를 확인합니다.

p의 가장 작은 소인수의 개수 2는 1개 입니다.

그럼 n은 p에서 공통으로 가장 작은 소인수인 2를 한번 더 곱한 값이기 때문에 n에서의 가장 작은 소인수인 2의 개수는 2개라고 할 수 있습니다.

이 값을 a라고 했을 때 

다음과 같은 식으로 n의 약수의 개수를 구할 수 있습니다.

 

만약 n과 p의 가장 작은 소인수가 서로 다른 경우

예를 들어 6은 6의 가장 작은 소인수가 2인데 6을 2로 나눈 3의 가장 작은 소인수는 3으로 서로 다릅니다.

그러면 6의 소인수에는 2가 1개밖에 존재하지 않기 때문에 factors[3]에 2를 곱해주면 6의 약수의 개수를 구할 수 있습니다. 그러므로 a를 1로 두면 위의 식과 동일하게 적용할 수 있습니다.

 

이렇게 소인수의 개수를 먼저 구하는 방식으로 문제를 해결하기 위해서는 에라토스테네스의 체 알고리즘을 사용하여 1부터 주어진 최대값인 1천만 까지 각 수의 가장 작은 소인수를 먼저 구해주면 됩니다.

 

 

구현 코드

 

	#include <iostream>
	#include <cmath>
	#include <cstring>
	using namespace std;
	//천만까지 가장 작은 소인수를 미리 minFactor에 계산
	const int MAX = 10000001;
	int minFactor[MAX];
	//i의 소인수 분해에 들어가는 minFactor[i]의 개수
	int minFactorPower[MAX];
	int factors[MAX];
	void getFactorSmart(){
	factors[1] = 1;
	for(int n=2;n<=MAX;++n){
	//소수인 경우 약수가 2개밖에 없다
	if(minFactor[n] == n){
	minFactorPower[n] = 1;
	factors[n] = 2;
	}
	//소수가 아닌 경우
	else{
	//n을 n의 가장 작은 소인수로 나눈다
	int p = minFactor[n];
	int m = n / p;
	//n과 m의 가장 작은 소인수가 서로 다른 경우에는 n의 소인수에 p가 1개만 존재한다
	if(p != minFactor[m])
	minFactorPower[n] = 1;
	//n과 m의 가장 작은 소인수가 서로 같은 경우에는
	//n의 소인수에 m의 가장 작은 소인수의 개수 + 1개가 존재한다
	else
	minFactorPower[n] = minFactorPower[m] + 1;
	int a = minFactorPower[n];
	factors[n] = (factors[m] / a) * (a + 1);
	}
	}
	}
	//에라토스테네스의 체를 사용하여 각 수의 가장 작은 소인수 구하기
	void eratosthenes(){
	//1은 예외처리한다
	minFactor[0] = minFactor[1] = 1;
	for(int i=2;i<=MAX;i++){
	minFactor[i] = i;
	}
	int sqrtn = int(sqrt(MAX));
	for(int i=2;i<=sqrtn;i++){
	if(minFactor[i] == i){
	for(int j=i*i;j<=MAX;j+=i){
	if(minFactor[j] == j)
	minFactor[j] = i;
	}
	}
	}
	}
	int main(){
	int test_case;
	int n,low,high;
	cin >> test_case;
	eratosthenes();
	getFactorSmart();
	while(test_case--){
	int count = 0;
	cin >> n >> low >> high;
	for(int i=low;i<=high;i++){
	if(n == factors[i]){
	count++;
	}
	}
	cout << count << endl;
	}
	}

view raw pass486.cpp hosted with ❤ by GitHub