[백준] 4134: 다음 소수

이번 문제는 백준 난이도 실버 4인 '다음 소수'문제이다.

 

테스트 케이스가 주어지면 그 수만큼 정수 입력을 반복해, 해당 정수보다 큰 소수 중 가장 작은 소수를 출력하는 문제이다.

 

소수란?

: 소수는 1과 자기 자신만을 약수로 가지는 수이다.

  예로 7, 13과 같은 수가 소수이다. → 7은 (1, 7), 13은 (1, 13)

 

추가로 합성수의 개념도 짚고 가자

합성수란?

: 합성수는 1과 자기 자신 외에도 약수를 가지는 수이다.

  편하게 4, 6, 12 등 여러 개의 약수를 가지는 수가 합성수라고 생각하면 된다.

 

그럼 소수를 구하는데 합성수의 개념은 왜 나온 걸까?

합성수는 N이라는 정수가 존재할 때, √N 이하의 약수를 무조건 하나 가진다.

예로 9라는 숫자가 있다면 √9 = 3이고. 9의 약수는 (1, 3, 9)이다 즉 3이하인 약수 3이 존재한다.

또 다른 예로 16을 들자면 √16 = 4이고, 16의 약수는 (1, 2, 4, 8, 16)이다 4이하인 약수 2, 4가 존재한다.

 

이렇게 합성수는 √N이하의 약수를 무조건 하나 이상 가진다는 특징을 가진다.

 

소수의 경우로 해보면 37이란 숫자가 있다면 √37 = 약 6이고 37을 2~6의 숫자까지 모두 나눠보아도 0으로 맞아떨어지는 수가 없다

 

즉, 어떤 수가 소수 인지 아닌지 판별하기 위해서는 해당 수의 √까지 순서대로 나눠보며 약수가 존재하는지 확인하면 알 수 있다.

 

---

코드로 구현해보자

 

[Python]

 

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

 

위에서 말한 조건인 √num +1 까지의 반복문 구조를 만들었다.

+1을 한 이유는 √했을때 올림 처리를 하기 위함이다.

 

입력된 숫자가 2이하인 0, 1인 경우에는 소수의 조건을 만족하지 않기 때문에 False를 리턴한다.

입력된 숫자에 √num+1 까지 순서대로 나눠보며 0으로 나눠떨어지는 경우가 있다면 False를 리턴한다. (합성수인 경우임)

위 경우들에 해당하지 않는다면 True를 리턴한다. (소수인 경우)

 

n = int(input())

result = []
for _ in range(n):
    num = int(input())
    while not is_prime(num):
        num += 1
    result.append(num)

for i in range(len(result)):
    print(result[i])

 

반복횟수 n을 입력받고 출력할 결괏값을 저장할 result리스트를 생성한다.

입력한 num부터 1씩 증가시키며 is_prime을 통해 해당 숫자가 소수인지 판별한다. 

추가한 결괏값들을 하나씩 출력하며 마친다.

 

<전체코드>

import sys
input = sys.stdin.readline

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

n = int(input())

result = []
for _ in range(n):
    num = int(input())
    while not is_prime(num):
        num += 1
    result.append(num)

for i in range(len(result)):
    print(result[i])