Lesson 12. Euclidean algorithm - CommonPrimeDivisors #1

1. 문제

A prime is a positive integer X that has exactly two distinct divisors: 1 and X. The first few prime integers are 2, 3, 5, 7, 11 and 13.
A prime D is called a prime divisor of a positive integer P if there exists a positive integer K such that D * K = P. For example, 2 and 5 are prime divisors of 20.
You are given two positive integers N and M. The goal is to check whether the sets of prime divisors of integers N and M are exactly the same.

For example, given:
N = 15 and M = 75, the prime divisors are the same: {3, 5};
N = 10 and M = 30, the prime divisors aren't the same: {2, 5} is not equal to {2, 3, 5};
N = 9 and M = 5, the prime divisors aren't the same: {3} is not equal to {5}.

Write a function:
  int solution(vector<int> &A, vector<int> &B);

that, given two non-empty arrays A and B of Z integers, returns the number of positions K for which the prime divisors of A[K] and B[K] are exactly the same.

For example, given:
A[0] = 15 B[0] = 75
A[1] = 10 B[1] = 30
A[2] = 3   B[2] = 5
the function should return 1, because only one pair (15, 75) has the same set of prime divisors.

Write an efficient algorithm for the following assumptions:
  - Z is an integer within the range [1..6,000];
  - each element of arrays A and B is an integer within the range [1..2,147,483,647].

 

두 수가 같은 소인수의 밑을 가지는 확인하는 문제.

같은 소인수의 밑을 가지는, 수의 쌍을 return하면 된다.

 

예시) return 1, 15와 75의 소인수 밑이 같다. 

N	Prime Divisors	M	Prime Divisors
15	\( 3, 5 \)	75	\( 3, 5^{2} \)
10	2, 5	30	2, 3, 5
3	3	5	5

 

 

2. 매개변수 조건

• Vector A, B size: 1 ~ 6,000
• Vector A, B 요소 값 범위: 1 ~ 2,147,483,647

 

3. 문제풀이 전략

• Vector A, B에서 가장 큰 값(max_value)을 구한다.
• max_value를 기반으로 에라토스테네스의 체(S)를 구성한다. (소인수를 구하기 위해)
• 에라토스테네스의 체를 이용해서, Vector A, B의 소인수를 구한다.

 

4. 코드 (C++)

에라토스테네스의 체(인수분해) 관련 알고리즘은 여기로

#include <map>
#include <cmath>

//소인수 구하기
map<int, int> GetPrimeDivisors(vector<int>& S, int n)
{
    map<int, int> divisors = {}; //map<base, exponent>

    while(S[n] > 0)
    {
        auto it = divisors.find(S[n]);
        if(it == divisors.end()) divisors.insert(pair<int, int>(S[n], 1));
        else it->second += 1;
        n /= S[n];
    }
    
    auto it = divisors.find(n);
    if(it == divisors.end()) divisors.insert(pair<int, int>(n, 1));
    else it->second += 1;

    return divisors;
}

int solution(vector<int> &A, vector<int> &B) {

    //max_value 찾기
    int max_value = 0;
    for(size_t i = 0; i < A.size(); i++)
    {
        int n = max(A[i], B[i]);
        if(n > max_value) max_value = n;
    }

    //max_value 기반으로 에라토스테네스의 체 구성
    vector<int> S(max_value + 1, 0);
    int n = 2;
    while(n <= sqrt(max_value) + 1)
    {
        int k = n * n;
        if(S[n] == 0)
        {
            while(k < max_value + 1)
            {
                if(k % n == 0) S[k] = n;
                k += n;
            }
        }
        n++;
    }

    //문제풀기
    int cnt = 0;   
    for(size_t i = 0; i < A.size(); i++)
    {
        //소인수 얻기
        map<int, int> div_a = GetPrimeDivisors(S, A[i]);
        map<int, int> div_b = GetPrimeDivisors(S, B[i]);

        //A, B가 같은 소인수를 갖는지 확인
        if(div_a.size() != div_b.size()) continue;

        bool same = true;
        auto it_a = div_a.begin();
        auto it_b = div_b.begin();
        while(it_a != div_a.end() && it_b != div_b.end())
        {
            if(it_a->first != it_b->first)
            {
                same = false;
                break;
            }

            it_a++;
            it_b++;
        }

        if(same) cnt++;
    }

    return cnt;
}

 

 

5. 결과

에라토스테네스의 체가 너무 커서, 메모리 할당 오류가 난다.