역시나 시간초과

1차 시도

#include <iostream>
using namespace std;

bool f(unsigned int n){
    unsigned int x = n - 1;
    
    while(x > 1){
        if(n % x == 0) return false;
        else x--;
    }

    return true;
}

int main(void) {
    int t = 0;
    cin >> t;

    for(int i = 0; i < t; i++){
        unsigned int n;
        cin >> n;

        while(true){
            if(f(n)) break;
            n++;
        }

        if(n < 2) n = 2;
        cout << n << endl;
    }

    return 0;
}

원래 이정도 난이도면 엄청 쉽게 푸는데.... 너무 오랜만에 잡으니까 감을 잃어버렸네요.

시간초과 솔루션

1. 소수 판별 순서변경

일단 n이 주워지면 100일때 99부터 나눠보면서 내려가는게 아니라 2부터 나눠서 소수인지 판별하는게 좀더 빠르게 나오지 않을까?

bool f(unsigned int n){
    unsigned int x = 2;
    
    while(x < n){
        if(n % x == 0) return false;
        else x++;
    }

    return true;
}

음 해결안됨.

2. 음 소수인지 아닌지를 메모제이션?

알고리즘 책에서 봤던거 같은데... 중복 연산을 피하기 위해서 메모제이션 해서 검사를 통과 시키면 될 것 같은데..

시간 부족해서 구현 안 함.

3. 음 소수에 배수를 곱하면 그 수들은 소수가 아니라는 그런 내용이 있었던거 같은데...

정답 찾아본 결과.

n의 값에(입력 값) 제곱근까지만(소수를 계산할 때) 계산하면 풀리는 문제고,

입력이 0과 1도 포함이라서 여기서 실수가 많이 나오는 것 같은데..
나는 if(n < 2) n = 2; 이 형식으로 미리 해결을 했어서 시간 초과만 나왔던것 같다.