[정수론] PASS486 비밀번호 456

#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
 
const int MAX_N = 10000001;
int minfac[MAX_N];
int testCase, n, lo, hi;
 
void era()
{
    for(int i = 2; i < MAX_N; i++) minfac[i] = i;
 
    minfac[0] = minfac[1] = -1;
 
    int sqrtn = sqrt(MAX_N-1);
    for(int i = 2; i <= sqrtn; i++)
    {
        if (minfac[i] == i)
        {
            for (int j = i*i; j <MAX_N; j+=i)
                if(minfac[j] == j)
                    minfac[j] = i;
        }
    }
}
 
int numOfdivisor(int pass)
{
    int mul = 1;
    int sum = 0;
    int before = minfac[pass], current;
    while(pass>1)
    {
        current = minfac[pass];
 
        if(current == before) sum++;
        else
        {
            mul = mul*(sum+1);
            sum = 1;
        }
        before = current;
        pass /= minfac[pass];
        if(mul > n) return -1;
    }
    mul = mul*(sum+1);
    return mul;
}
 
int pass()
{
    int count = 0;
   for(int i = lo; i <= hi; i++)
    {
        if(n == numOfdivisor(i)) count++;
    }
    return count;
}
 
int main()
{
    era();
    cin>>testCase;
    for(int i = 0; i < testCase; i++)
    {
        cin>>n>>lo>>hi;
        cout<<pass()<<"\n";
    }
}

1. 풀이

 

에라토스네스의 체를 이용하여

숫자의 약수중 가장 작은 소수를 따로 저장했다.

 

그리고 찾는 범위의 숫자들을  가장 작은 소수들로 1이 될때까지 나누면서

소수들의 개수를 세었다.

 

약수의 수 = Π(소수의 지수 + 1) 

 

2. 책의 풀이1

 

책에서도 똑같이 에라토스네스의 체를 이용하였지만

 

가장작은 소수를 나누고 난 그 수와의 관계를 통해

 

약수의 개수를 모두 구해 따로 저장하였다.

 

n의 가장 작은 소인수가 p이고, 이 소인수가 a번 출현한다면 다음과 같다

factor(n) = factor(n/p) * (a+1)/a 

 

3. 책의 풀이2

 

이 풀이도 에라토스네스의 개념을 이용한 것이다.

수를 지우는게 아니라

해당하는 배수에 +1을해 약수의 개수를 카운트하는 것이다.

 

 

- 알고리즘 문제해결전략 506p

PASS486