< 백준 BaekJoon : 4134번 다음 소수> C++

<<문제>>

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

4134번: 다음 소수

 

제곱근까지 나누어 봤을 때 나누어 떨어지는지를 판별하는 방법으로 해결 가능

 

 

 

 

<<코드>>

#include <iostream>
using namespace std;

bool isPrime(long long int num) {
  if (num == 0 || num == 1)
    return false;

  if(num == 2) return true;
  else if (num % 2 == 0)
    return false;
  
  for (long long int i = 3; i * i <= num; i += 2) {
    if (num % i == 0) {
      return false;
    }
  }

  return true;
}

long long int targetPrime(long long int num) {
  // 0과 1인 경우를 특정
  while (!isPrime(num)) {
    num++;
  }
  return num;
}

int main() {
  int testNum;
  cin >> testNum;

  long long int inputNum;
  for (int i = 0; i < testNum; i++) {
    cin >> inputNum;
    cout << targetPrime(inputNum) << endl;
  }
}