[BOJ | Python] 4134번: 다음 소수

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

 

문제

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

 

 

입력

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

 

 

출력

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

 

풀이

def isPrime(n):
    if n <= 1: return False
    elif n <= 3: return True
    else:
        for i in range(2, int(n**0.5) + 1):
            if not n % i: return False
        return True

for _ in range(int(input())):
    n = int(input())

    while not isPrime(n):
        n += 1

    print(n)

 

[isPrime 함수]

소수를 판별하는 함수로, n이 소수면 True를, 그렇지 않다면 False를 반환한다.

0, 1 -> 소수 X

2, 3 -> 소수 O

이 정도만 조건문으로 처리한 후 나머지는 반복문을 사용해 나머지가 0이 되는 수가 있는지를 확인하여 소수를 판별한다.

 

[main]

테스트케이스만큼 반복하며, n을 입력받는다.

우리의 목표는 n 이상이면서 최소인 소수를 찾는 것이므로, n부터 1씩 증가하며 해당 수가 소수인지를 알아본다.

만약 소수라면 그대로 while문을 통과하여 n을 출력하고,

소수가 아니라면 n에 1을 더해 다시 소수 여부를 조사한다.