Lesson 12. Euclidean algorithm - CommonPrimeDivisors #2 (개선-1)

1. 이전 코드의 문제점

에라토스테네스의 체가 너무 커서, 메모리 할당에 실패했다.

 

2. 개선 아이디어

에라토스테네스의 체를 쓰지 않고, 2부터 N까지 하나씩 나눠가며 소인수를 찾는다.

 

3. 코드 (C++)

#include <cmath>
#include <map>

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

    int i = 2;
    while(i <= n)
    {
        if(n % i == 0) // i는 소인수
        {
            auto it = prime_divisors.find(i);
            if(it == prime_divisors.end())
            {
                prime_divisors.insert(pair<int, int>(i, 1));
            }
            else
            {
                it->second += 1;
            }

            // n을 i로 나누어서, n 값을 줄인다
            // 소인수 i가 여러번 쓰일수도 있기 때문에, i값을 증가시키면 안된다.
            n /= i;
        }
        else //i는 n의 소인수가 아니다
        {
            i++;
        }
    }

    return prime_divisors;
}

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

    int cnt = 0;

    for(size_t i = 0; i < A.size(); i++)
    {
        //예외처리
        if(A[i] == B[i])
        {
            cnt++;
            continue;
        }

        //A[i], B[i], 소인수 구하기
        map<int, int> div_a = GetPrimeDivisors(A[i]);
        map<int, int> div_b = GetPrimeDivisors(B[i]);

        //예외처리, 개수가 같지 않으면 소인수의 밑이 같을 수 없다
        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;
}

 

4. 결과