본문 바로가기

programming/algorithm

[algorithm] 백준 4134 다음 소수

[algorithm] 백준 4134 다음 소수

 

안녕하세요. 심심한 코딩쟁이입니다.
 
오늘 백준 4134 다음 소수 문제에 대해 설명을 드리겠습니다.
 
파이썬3 를 사용해 문제 풀이를 진행하겠습니다.
 
문제 링크를 걸어두었으니 문제를 살펴보시고 문제를 푼 다음에 저와
 
풀이를 비교해 보시는 걸 추천드립니다.

차근차근 풀어봅시다.

 

algorithm
알고리즘


백준 BAEKJOON 4134

 

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

 

 

4134번: 다음 소수

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

www.acmicpc.net

 

문제 해석

 

테스트 케이스로 주어지는 수보다 크거나 같은 소수 중 가장 작은 소수를 출력하는 문제입니다.

정수론의 개념인 "임의의 양수 A가 합성수이면 √A 보다 작거나 같은 약수를 가진다." 를 활용하면

소수의 조건을 다음과 같이 생각해 볼 수 있습니다.

임의의 양수 A가 √A 보다 작거나 같은 약수를 가지지 않으면 소수이다.

위 개념을 잘 이용해서 문제를 풀어봅시다.

 

풀이

 

import sys

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

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

for i in range(t):
    n = int(input())
    while True:
        if n == 0 or n == 1:
            print(2)
            break
        if is_prime(n):
            print(n)
            break
        else:
            n += 1

 

풀이 해석 및 팁

 

n이 0 또는 1일 때는 2를 출력하고

n이 √n 보다 작거나 같은 약수를 가지지 않으면 소수이므로 n을 출력

n이 √n 보다 작거나 같은 약수를 가지면 소수가 아니므로 n에 1을 더하고 윗줄의 과정으로 돌아간다.

이를 계속 반복하다보면 가장 가까운 소수를 찾을 수 있습니다.

여기까지 백준 4134번 다음 소수 문제에 대한 설명이었습니다.

 

궁금하신 점이나 도움이 필요한 부분이 있으시다면 언제든지 댓글로 남겨주시기 바랍니다.

 

감사합니다.

반응형