[백준/Python] 4134 다음 소수

[백준/Python] 4134 다음 소수

풀이 코드 및 설명

def is_prime(n):
    if n <= 1: 
        return False
    if n <= 3: 
        return True
    if n % 2 == 0 or n % 3 == 0: 
        return False
    i = 5 
    while i * i <= n: 
        if n % i == 0 or n % (i + 2) == 0: 
            return False
        i += 6
    return True

def next_prime(n):
    while True:
        if is_prime(n):
            return n
        n += 1

test_case_number = int(input())

for _ in range(test_case_number):
    n = int(input())
    result = next_prime(n)
    print(result)

문제를 풀기 위해서 접근 방법은 다음과 같다.

1. 케이스 입력 만큼 반복
2. 입력 받은 n 에 대해서 다음 소수를 찾는다.
   2 - 1. 다음 소수를 찾는 방법은 다음과 같다
   2 - 2. n 을 1증가 시키면서 소수를 만족하는 가장 작은 수를 찾으면 된다.

def next_prime(n):
    while True:
        if is_prime(n):
            return n
        n += 1

다음 소수를 찾는 함수이다. n을 매개 변수로 실행 시키며 반복문으로 소수인지 판단하는 is_prime(n) 을 호출한다. 이 함수의 반환 값이 True 라면 n 을 반환한다. 이 n 값이 바로 소수이기 때문이다. 만약 True 가 아닌 False 일 경우에는 n 이 소수가 아니라는 뜻이므로 n 값을 1 증가 시키면 된다.

제일 중요한 건 소수인지 아닌지 판별하는 함수 is_prime 이다.

def is_prime(n):
    if n <= 1: 
        return False
    if n <= 3: 
        return True
    if n % 2 == 0 or n % 3 == 0: 
        return False
    i = 5 
    while i * i <= n: 
        if n % i == 0 or n % (i + 2) == 0: 
            return False
        i += 6
    return True

n 을 매개 변수로 하는 is_prime 함수는 다음과 같다.
1. 먼저 1 이하의 수를 처리한다. 소수는 1과 1보다 작은 수는 소수가 아니기 때문에 소수가 아니다 -> Flase 를 반환한다.
2. 2와 3 처리한다. 2와 3은 가장 작은 소수이므로 이 경우 별도로 처리해준다.
3. 2와 3의 배수를 제거한다. 이 경우 소수가 아니기 때문에 False를 반환한다.
4. 5 이상의 수를 처리한다.
5. while 반복문에서 i * i <=n 이라는 조건하에 반복하게 된다. 이는 n의 제곱근 까지만 검사하면 충분하기 때문이다. n의 약수는 n의 제곱근 이하에서 발견되기 때문이다.
6. 나머지 수들에 대해서 소수를 판별한다.
6-1. n % == 0 이 조건은 n 이 i 로 나누어 떨어지는 지 확인한다. 이 경우 소수가 아니다.
6-2. n % (i+2) 이 부분은 2와 3의 배수를 미리 제외한 남은 수를 검사하기 때문이다. 2와 3의 배수를 제외한 남은 수들은 6k +- 1의 형태를 가진다. k는 양의 정수이다. 즉, 6의 배수보다 1작거나 1 큰 수를 뜻한다. i 가 현재 5부터 시작이다. i는 6k - 1을 뜻한다.
6-3. i 가 6k - 1 을 뜻한다면, 6k + 1 을 뜻하는 것은 i(6k - 1) + 2 이기 때문이다.
6-4. 검사가 끝났다면 i를 6 증가 시킨다. 왜냐하면 6k +- 1 에서 k 가 1일때 5,7 k가 2일 때 11, 13 이다. 5 -> 11 6이 증가하였고, 7 -> 13 6이 증가하기 때문이다.
6-5. 2와 3의 배수를 제외하는 이유는 효율적으로 소수를 검사하기 위함이다.