Problem 5

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define NUM 20

// 素数テーブルの作成
void
primeTable(int l, bool t_prime[])
{
    unsigned int size = (unsigned int)ceil(sqrt((double)NUM)); // 篩の大きさ
    memset(t_prime, true, NUM);

    // 篩にかける
    t_prime[0] = t_prime[1] = false;
    for (unsigned int i = 2; i <= size; i++)
    {
        if (t_prime[i])
        {
            for (unsigned int j = i+i; j < NUM; j+=i)
            {
                t_prime[j] = false;
            }
        }
    }
}

int
main(int argc, char ** argv)
{
    vector<int> v_pf; // 素因数
    bool *t_prime = new bool [NUM];

    // 素数テーブルを作る
    primeTable(NUM, t_prime);

    for (int i = NUM; i >= 1; i--)
    {
        int n = i;
        
        // 素因数分解
        for (int i = 0; i < NUM; i++)
        {
            if (t_prime[i])
            {
                int pf = 0;
                while (1)
                {
                    if (n%i == 0)
                    {
                        pf++;
                        n /= i;
                    }
                    else
                    { 
                        // 重複していない分を追加
                        vector<int>::iterator pos = v_pf.begin();
                        for (int j = 0; j < pf; j++)
                        {
                            pos = find(pos, v_pf.end(), i);
                            if (pos == v_pf.end())
                            {
                                v_pf.push_back(i);
                                pos = v_pf.end();
                            }
                            pos++;
                        }
                        break;
                    }
                }
            }
        }
    }

    int ans = 1;
    for (vector<int>::iterator it = v_pf.begin(), end = v_pf.end(); it != end; it++)
    {
        ans *= *it;
    }
    cout << ans << endl;

    return 0;
}