백준 4134번 풀이

문제

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

4134번: 다음 소수

주어진 숫자보다 같거나 큰 소수를 출력하시오. (예: 6->7)

 

풀이

이 문제를 풀기 위해서는 필요한 게 하나 있다.

def isprime(a):
    sqrt = int(a ** 0.5)
    if a == 1: 
        return False
    for i in range(2,sqrt+1):
        if a % i == 0:
            return False
    else: 
        return True

바로 에라토스테네스의 체를 예전에 백준 푼다고 루트 N 버전으로 코딩한게 그것. 근데 저거 저대로 쓰면 틀리고요… 내 경험담임 님들은 한방에 맞추십셔…

 

def isprime(a):
    sqrt = int(a ** 0.5)
    if a < 2: 
        return False
    for i in range(2,sqrt+1):
        if a % i == 0:
            return False
    else: 
        return True

아무튼 0이랑 1은 애초에 소수고 나바리고 못 매기니까 걍 예외처리 합시다.

 

K = int(sys.stdin.readline())

for i in range(K):
    T = int(sys.stdin.readline())
    while isprime(T) == False:
        T += 1
    print(T)

우리 늘 그래왔듯이… 입력은 쉽다. 로직이 문제지… 근데 문제를 보면 주어진 수보다 '같거나 큰' 소수를 출력하라고 되어 있다. 그래서 체 갖고왔잖아요? 그리고 같거나 큰 소수를 찾기 위해 저 체를 쓸 거다. 같거나 큰 소수가 나올때까지 뺑뺑이를 돌려야 하니 반복문으로 While이 온 거고. 여기까지 이해 되셨죠?

 

isprime()에 소수를 넣었을때는 True, 합성수를 넣었을때는 False가 나온다. 그럼 왜 While문에 저런 조건이 붙었는지도 이해할 수 있다. False 떴으면 합성수니까 1을 더해서 소수 나올때까지 반복문 뺑뺑이 돌라는 얘기. 쉽죠?

 

import sys

def isprime(a):
    sqrt = int(a ** 0.5)
    if a < 2: 
        return False
    for i in range(2,sqrt+1):
        if a % i == 0:
            return False
    else: 
        return True
    
K = int(sys.stdin.readline())

for i in range(K):
    T = int(sys.stdin.readline())
    while isprime(T) == False:
        T += 1
    print(T)

그래서 이거 내고 맞았다.