[Baekjoon] 3896. 소수 사이 수열 [S1]

📚 문제

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

특정 숫자를 선택하면 그 숫자랑 가장 가까운 소수 두 수의 거리를 출력하는 문제이다.

소수를 골랐을 경우는 0을 출력한다.

1299709 소수까지이니 별로 크지 않아 에라토스테네스의 체를 활용해 소수의 배수를 1로 바꿔주며 소수만 0으로 남긴다.

0으로 초기화하여 배열을 선언하고 2부터 순서대로 순회한다.

0이 나오면 i의 배수를 전부 합성수인 1로 처리해주면 된다. 이 때 가지치기를 위해 i * i부터 배수를 곱해주는 방법을 사용한다. 왜냐면 i보다 작은 배수들은 이미 전에 처리됐기 때문이다.

ex). i가 5인 경우 5 * 2는 2의 배수에서 처리했고 5 * 3은 3의배수에서 처리했다. 따라서 5 * 5부터 1로 바꿔주면 된다.

위 과정을 반복하여 소수만 0인 배열을 다 만들어준다.(0, 1은 소수가 아닌데 0이다. 그렇지만 사용하지않으므로 놔둔다.)

이제 입력받은 숫자가 소수이면 0을 출력하고, 입력받은 숫자가 합성수면 델타 탐색을 활용한다.

왼쪽과 오른쪽으로 움직이며 소수를 만난경우 멈춘다. 둘 다 현재 소수이면 차이를 출력한다.

📒 코드

T = int(input())
arr = [int(input()) for _ in range(T)]
max_num = max(arr)
arr_check = [0 for _ in range(1299710)]     # 소수 판정 소수면 0
                                            # 0, 1도 소수가 아니지만 안쓰니까 그냥 둔다.
for i in range(2, 1299710):                 # 에라토스테네스의 체 배열 구현
    if arr_check[i] == 0:                   # 소수 발견
        if max_num <= i:                     # max_num 보다 크거나 같은 소수를 만나면 종료
            break
        for j in range(i*i, 1299710, i):    # 소수가 아닌 수에 1로 변경
            arr_check[j] = 1                # i보다 작은 수로 곱하는 경우는 이미 나왔다.


for i in arr:
    if arr_check[i]:    # 합성수일경우 왼쪽 오른쪽 소수를 찾는다.
        dl = i - 1      # 왼쪽 탐색
        dr = i + 1      # 오른쪽 탐색
        while arr_check[dl] or arr_check[dr]:   # 왼쪽과 오른쪽 다 소수를 만났을 때 탈출
            if arr_check[dl]:       # 소수가 아니면 왼쪽으로 1칸 이동
                dl -= 1
            if arr_check[dr]:       # 소수가 아니면 오른쪽으로 1칸 이동
                dr += 1
        print(dr - dl)              # 두 소수의 길이 출력
    else:                           # 소수일 경우 0 print
        print(0)

🔍 결과