[알고리즘] 백준 3896 파이썬 - 소수 사이 수열

 

3896번: 소수 사이 수열

문제

연속한 소수 p와 p+n이 있을 때, 그 사이에 있는 n-1개의 합성수(소수나 1이 아닌 양의 정수)는 길이가 n인 소수 사이 수열라고 부른다.

양의 정수 k가 주어졌을 때, k를 포함하는 소수 사이 수열의 길이를 구하는 프로그램을 작성하시오. k를 포함하는 소수 사이 수열이 없을 때는 길이가 0이다.

예를 들어, 소수 23과 29의 소수 사이 수열은 {24, 25, 26, 27, 28}이고, 길이는 6이다.

 

 

문제풀이

import sys
input = sys.stdin.readline
#01
n=1299709
dp=[False,False]+([True]*(n-1))
for i in range(2,n+1):
    for j in range(i*2,n+1,i):
        dp[j]=False
#02
for _ in range(int(input())):
    k=int(input().rstrip())
    if(dp[k]):
        print(0)
    #03
    else:
        cnt=0
        for i in range(k,len(dp)):
            if dp[i]:
                break
            cnt+=1
        for j in range(k,-1,-1):
            if dp[j]:
                break
            cnt+=1
        #04
        print(cnt)

- 이 문제도 에라토스테네스의 체를 활용하여 풀었다.

[알고리즘] 백준 17103 파이썬 - 골드바흐 파티션(에라토스테네스의 체)

- #01 : n까지 에라토스테네스의 체를 사용하여 dp에 소수를 True로 저장한다.

- #02 : 입력받은 k값이 True(소수)일 경우 0을 출력한다.

- #03 : False(합성수)일 경우, k부터 다음 소수까지 개수를 cnt에 추가해주고,

           k부터 이전 소수까지의 개수를 cnt에 추가해준다.

- #04 : 최종적으로 소수 이전 배열의 길이를 출력해준다.