大神的世界

建立質數表

輸入數字

將其作質因數分解並相加

判別數字是否為1

(因為測資超出範圍)

是

輸出sum

否

輸出sum + 剩餘的數字

#include <iostream>
#include <cstring>
#include <vector>

#define N 20000000

typedef unsigned long long int ulli;

using namespace std;

bool Bprime[N];
vector <int> Vprime;

void setPrimeTable()
{
    Vprime.clear();
    memset(Bprime, true, N);
    Bprime[0] = Bprime[1] = false;

    for(int i = 2; i<N; i++)
    {
        if(Bprime[i])
        {
            Vprime.push_back(i);

            for(int j = i; j<N; j+=i)
                Bprime[j] = false;
        }
    }
}

int main()
{
    setPrimeTable();

    int x;
    ulli sum;

    while(cin >> x)
    {
        sum = 0;
        for(int i = 0; i<Vprime.size() && x > 1; i++)
            while(x%Vprime[i] == 0)
            {
                x/= Vprime[i];
                sum += Vprime[i];
            }

        if(x == 1)
            cout << sum << endl;
        else
            cout << sum + x << endl;
    }

    return 0;
}