[BOJ/백준/C++] 4134번 다음 소수

4134번: 다음 소수

---

반응형

📌 접근 방법

🚫 시간초과

• 반복문을 사용하여 n까지 돌려보며 n 이상의 소수를 찾아보았더니 시간초과가 나왔다
• long long 사용
• 반복문에서 i*i를 사용하면 i까지만 반복하면서 모든 경우를 한 번에 확인할 수 있습니다.
  •  i*i가 n보다 작거나 같을 때까지만 반복하고 있다
  • 반복 횟수를 줄일 수 있고, 성능을 향상시킬 수 있.

 

✅  Pass Code

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iterator>
#include<map>
#include<set>
using namespace std;
typedef unsigned long long INT;
bool prime(INT n){
    if(n<=1)return false;
    for(INT i=2; i*i<=n; i++){
        if(!(n%i))return false;
    }
    return true;
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    INT n,k;
    cin>>n;
    while(n--){
        cin>>k;
        
        while(!prime(k)){
            k++;
        }
        cout<<k<<"\n";
    }

    return 0;
}