[BOJ][⚪1][백준#03896] 소수 사이 수열

문제 출처

BAEKJOON Online Judge #3896

문제

연속한 소수 p와 p+n이 있을 때, 그 사이에 있는 n-1개의 합성수(소수나 1이 아닌 양의 정수)는 길이가 n인 소수 사이 수열라고 부른다. 양의 정수 k가 주어졌을 때, k를 포함하는 소수 사이 수열의 길이를 구하는 프로그램을 작성하시오. k를 포함하는 소수 사이 수열이 없을 때는 길이가 0이다. 예를 들어, 소수 23과 29의 소수 사이 수열은 {24, 25, 26, 27, 28}이고, 길이는 6이다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 테스트 케이스는 한 줄로 이루어져 있고, 한 줄에 정수 k가 주어진다. 각각의 정수는 1보다 크고, 100000번째 소수(1299709)와 작거나 같다.

출력

각각의 테스트 케이스에 대해서 k가 합성수라면 k를 포함하는 소수 사이 수열의 길이를 출력한다. 그렇지 않으면 0을 출력한다.

예제

입력

5
10
11
27
2
492170

출력

4
0
6
0
114

My Sol

import sys
input = sys.stdin.readline

def check(N):
    global arr
    cnt = 0
    l = r = N
    while not arr[l]:
        cnt += 1
        l -= 1

    while not arr[r]:
        cnt += 1
        r += 1

    return cnt

N = int(input())
inputs = [int(input()) for _ in range(N)]
M = 1299710
arr = [1]*M
arr[0] = arr[1] = 0
for a in range(2, M):
    if arr[a]:
        for b in range(a+a, M, a):
            arr[b] = 0

for n in inputs:
    print(check(n))

아르키메데스의 체 공식을 활용하여 전체 소수 체크 배열을 만들고, 2부터 시작해서 1인 값을 만나면 그 수의 배수인 이후의 수들을 모두 0으로 체크한다. 이렇게 되면 뒤의 어떠한 값이 1인 경우 이전에 나온 수들의 배수가 아니기 때문에 소수이다.

이렇게 소수 배열을 만들고, 각각의 합성수에 대해 앞과 뒤로 1을 만날 때까지 cnt를 더해준다. 이러면 구간의 길이를 구할 수 있다. 이를 출력한다.

결과

맞았습니다!!

모범답안

출처

import sys
input = sys.stdin.readline

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

for _ in range(int(input())):
    k = int(input())
    if is_prime(k):
        print(0)
    else:
        s,e = k-1, k+1
        while not is_prime(s):
            s -=1
        while not is_prime(e):
            e +=1
        print(e-s)

연산 시간이 40% 정도인 풀이를 발견해 풀이를 분석해보려 한다. 소수 배열을 만들지 않고, 소수인지 확인하는 is_prime 함수를 만들어 사용하셨다. 2부터 자기 자신의 제곱근까지로 나누었을 때 나머지가 0인 경우라면 소수가 아니고, 나머지가 0인 경우가 한 번이라도 없으면 소수이다.

이를 매번 체크하는데, 매번 같은 연산을 반복해 시간이 오래 걸릴 것 같으면서도 생각보다 빠르게 체크가 되는가보다. 크기가 100만정도인데, 제곱근은 그러면 1000 정도이므로 체크가 빠르게 되는 것 같다. 더군다나 짝수라면 2에서 바로 소수 체크가 되므로 예상보다는 빠른 체크가 가능한 것으로 보인다.

좋은 풀이였다.