[백준/파이썬] 3896번 소수 사이 수열 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 3896번 소수 사이 수열
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

주어진 수 n을 포함하는 소수 구간에서 양쪽 가장 가까운 소수의 차이를 구하는 문제입니다.

코드

from sys import stdin

for _ in range(int(stdin.readline())):
    n = int(stdin.readline())

    start = n;
    end = n;
    sf = False
    ef = False

    while True:
        if not sf:
            sp = True
            for i in range(2, int(start**0.5)+1):
                sp = start % i != 0
                if not sp:
                    break
            sf = sp
                
        if not ef:
            ep = True
            for i in range(2, int(end**0.5)+1):
                ep = end % i != 0
                if not ep:
                    break
            ef = ep
        if sf and ef:
            break
        if not sf:
            start -= 1
        if not ef:
            end += 1
    print(end-start)

설명

n에서 아래/위로 각각 확장하면서 소수 여부를 검사해 양쪽 소수를 찾은 뒤 차이를 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---