[백준/Python] 4134번 : 다음 소수

4134번: 다음 소수

시간 제한	메모리 제한	문제 티어	정답 비율
1 초	128 MB	실버 IV	25.145%

📜 문제

정수 n(0 ≤ n ≤ 4*10^9)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.

 

📥입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

 

 

📤출력

각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다.

 

💡풀이

기본적으로 해당 num이 소수인지 확인하는 알고리즘 풀이법은 총 3가지가 있다.

 

1. 아예 num을 2부터 num까지 나누어서 확인하는 알고리즘 => 시간복잡도 O(n)

2. num을 2부터 num/2까지 나누어서 확인하는 알고리즘 => 시간복잡도 O(n)

3. num을 2부터 √num 까지 나누어서 구하는 알고리즘(num의 약수의 중간을 구하는 원리) => 시간복잡도 O(√n)

 

나는 3번째 방법을 사용해서 is_prime() 함수를 만들어줬고, num이 소수가 아닐 경우 next_num() 함수에서 다음 num으로 넘어가 다시 소수를 확인하는 식으로 아래와 같이 코드를 작성했다. 

import sys
import math

def is_prime(num):
  if num == 0 or num == 1:
    return False
  else:
    for i in range(2, int(math.sqrt(num)) + 1):
      if num % i == 0:
        return False
    return num

def next_num(num):
  while True:
    if is_prime(num) == False:
      num += 1
    elif is_prime(num):
      return num

input = sys.stdin.readline

times = int(input())

for _ in range(times):
  num = int(input())
  print(next_num(num))