Codeforces Round #641 (Div.2) A. Orac and Factors

f(n)은 n을 나누는 가장 작은 소수를 출력한다. 에라스토테네스의 체를 사용하여,  10^6 까지의 n에 대하여 f(n)을 구한다. 코드에서는 minDiv배열에 해당값을 저장하였다.

n = f(n) + n 을 k번 반복한다. test case의 수가 100개 k가 10^9 개 이므로 k번 반복해서는 time out이 발생한다. 

두번째 계산부터 f(n)은 무조건 2인데, 이는 f(n) + n의 값이 무조건 짝수이기 때문이다. f(n)이 홀수 일경우 n도 홀수이고, f(n)이 짝수인경우는 n또한 짝수이다.

이를 통해 답을 계산하면, ans = f(n) + n + (k-1) * 2 가 된다.

#include<iostream>

using namespace std;
int minDiv[1000010];

int main(){
    int t;
    cin >> t;
    for(int i = 0; i < 1000010; i ++){
        minDiv[i] = i;
    }
    for(int i = 2; i * i < 1000010; i ++){
        if(minDiv[i] == i){
            for(int j = i * i; j < 1000010; j += i){
                if(minDiv[j] == j) minDiv[j] = i;
            }
        }
    }

    while (t --){
        int n,k;
        cin >> n>> k;
        //k-1개 항목은 전부 짝수이므로 2를 더해준다.
        n = n + minDiv[n] + (k-1) * 2;
        cout << n << endl;
    }
    return 0;
}