UESTC 1246 拆x3

用归纳法分析可以知道死循环只有4。

分析一下复杂度，如果n很大并且不是素数，根据基本不等式可以知道 sum factor(n) ≥ 2+n/2 ≈ n/2。

复杂度是O(T*logN*sqrt(N))，这个上界比较松。如果是用Pollard_rho再开个平方估计常数也差不多了。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;


int decompose(int x, bool &is_pm)
{
    int re = 0;
    for(int i = 2; i*i <= x; i++){
        while(x % i == 0){
            re += i; x /= i;
        }
    }
    is_pm = !re;
    if(x > 1) {
        re += x;
    }
    return re;
}


//#define LOCAL
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    int x, y;
    bool is_pm;

    while(~scanf("%d", &x)){
        if(x == 4) puts("-1");
        else {
            while(true){
                y = decompose(x, is_pm);
                if(is_pm) break;
                x = y;
            }
            printf("%d\n", x);
        }
    }
    return 0;
}