(4134) 다음 소수

https://www.acmicpc.net/problem/4134

단계별로 풀어보기

15단계(약수, 배수와 소수 2) 5번째

 

 

 

브루트 포스로 풀어도 된다는 증명이 있긴 한데 알고리즘보다 정수론 지식이 더 필요한 증명 같아서 패스. 그냥 되겠거니 하고 풀면 될 것 같다.

그것보다 1 이하 예외처리를 안해서 틀렸다.

 

 

 

#include <iostream>
using namespace std;
typedef unsigned int ui;

bool isprime(ui x){
  if(x<=1)  return false;
  
  for(ui i=2;i*i<=x;i++){
    if(x%i==0)  return false;
  }
  
  return true;
}

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    ui n;
    
    cin >> n;
    
    while(true){
      if(isprime(n)){
        cout << n << "\n";
        
        break;
      }
      
      n++;
    }
  }
  
  return 0;
}