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

백준 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번 다음 소수 문제에 대한 설명이었습니다.
궁금하신 점이나 도움이 필요한 부분이 있으시다면 언제든지 댓글로 남겨주시기 바랍니다.
감사합니다.
반응형
'programming > algorithm' 카테고리의 다른 글
[algorithm] 백준 4948 - 베르트랑 공준 (0) | 2023.04.01 |
---|---|
[algorithm] 백준 1929 - 소수 구하기 (0) | 2023.03.31 |
[algorithm] 백준 단계별 문제 풀이 (약수, 배수와 소수 2 - 1탄) (0) | 2023.03.27 |
[algorithm] 백준 단계별 문제 풀이 (집합과 맵 2탄) (0) | 2023.03.25 |
[algorithm] 백준 단계별 문제 풀이 (집합과 맵 1탄) (0) | 2023.03.24 |