/*
 * @lc app=leetcode.cn id=650 lang=cpp
 *
 * [650] 只有两个键的键盘
 */
#include <bits/stdc++.h>
using namespace std;
// @lc code=start
class Solution
{
    vector<int> primes_factors; //质因数表，按从小到大的顺序存放着n的所有因数
    vector<bool> isPrimes;      //质数筛，数字对应下标的值为1则为质数，反之则不是质数

    void findPrimesFactors(const int n) //找到n的所有质因数（存入primes_factors中）
    {
        for (int i = 2; i <= n; i++) //从2开始，找到所有小于等于的质数
        {
            if (isPrimes[i] == 0)                //如果i是合数
                continue;                        //则跳过
            else                                 //否则i是质数
                if (n % i == 0)                  //判断i是不是n的因数
                {                                //如果是
                    primes_factors.push_back(i); //就存入质因数表中
                    findPrimesFactors(n / i);    //找到因数i并存储后，问题缩小为找到n/i的质因数
                    return;                      //子问题解决后，原问题就解决了
                }
                else                                   //如果不是，就筛掉i的倍数
                    for (int j = i * 2; j < n; j += i) // i的倍数都是合数，将其筛去
                        isPrimes[j] = 0;
        }
    }

public:
    int minSteps(int n)
    {
        //要操作的次数 = (n的所有因数的值 - 1) + 因数的个数
        //每遇到一个因数执行一次copy all，再执行x次paste，以此让原有数字的个数变为原来的x倍，即扩大x-1倍，所以x=因数的值-1
        //由于一次copy all要+1，一次paste要-1，所以要操作的次数=n的所有因数的值之和

        isPrimes.resize(n + 1, 1); //质数筛的大小为n+1（多一个表示n是否为质数），将其元素初始化为1，之后不断筛去合数
        findPrimesFactors(n);      //找n的质因数；只有小于等于根号n的数才有可能成为n的因数；且n的因数都是小于等于根号n的数

        return accumulate(primes_factors.begin(), primes_factors.end(),0);
    }
};
// @lc code=end