Project Euler #5 - Smallest multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

출처: https://projecteuler.net/

1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수를 구하는 문제입니다. 

이는 1~20 까지의 최소공배수를 구하는 방법으로 풀 수 있습니다. 최소 공배수를 구하는 방법에는 여러 가지가 있는데, 소인수분해를 이용하는 방법을 사용했습니다. 방법은 각 수를 모두 소인수분해한 후 공통인 소인수 중에서 거듭제곱의 지수가 큰 것을 선택하고, 나머지 공통이 아닌 소인수까지 모두 곱하면 됩니다. 

소인수분해는 특정한 수의 소인수분해를 하는 것이 아니라 1~n의 소인수분해된 값을 얻어야 되기 때문에 Eratosthenes' sieve 방법을 사용하여 구했습니다.

my solving

c++

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
 
 
int minPrimeFactors[30];
 
void eratosthenes(int maxNum) 
{
    minPrimeFactors[0] = minPrimeFactors[1] = -1;
 
    for (int i = 2; i <= maxNum; i++)
        minPrimeFactors[i] = i;
 
    int sqrtn = int(sqrt(maxNum));
 
    for (int i = 2; i <= sqrtn; i++)
    {
        if (minPrimeFactors[i] == i) 
        {
            for (int j = i * i; j <= maxNum; j += i)
            {
                if (minPrimeFactors[j] == j)
                    minPrimeFactors[j] = i;
            }
        }
    }
}
 
map<int, int> getPrimeFactor(int num) 
{
    map<int, int> ret;
 
    while (num > 1) 
    {
        map<int, int>::iterator it = ret.find(minPrimeFactors[num]);
 
        if (it == ret.end())
            ret.insert(make_pair(minPrimeFactors[num], 1));
        else
            ret[minPrimeFactors[num]]++;
        
        num /= minPrimeFactors[num];
    }
    return ret;
}
 
 
int main() 
{
    int maxNum = 20;
    eratosthenes(maxNum);
 
    ll ret = 1;
 
    map<int, int> primes;
 
    for (int i = 2; i <= maxNum; i++)
    {
        map<int, int> temp = getPrimeFactor(i);
 
        for (map<int, int>::iterator it = temp.begin(); it != temp.end(); it++)
        {
            map<int, int>::iterator it2 = primes.find(it->first);
 
            if (it2 == primes.end())
                primes.insert(make_pair(it->first, 1));
            else
            {
                if (it->second > primes[it->first])
                    primes[it->first] = it->second;
            }
        }
    }
 
    for (map<int, int>::iterator it = primes.begin(); it != primes.end(); it++)
    {
        ret *= (pow(it->first, it->second));
    }
 
 
    cout << ret << endl;
 
    system("pause");
    return 0;
}