[백준] 17394 핑거 스냅 (Python)

 

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

17394번: 핑거 스냅

이문제는 BFS + 소수판별 알고리즘 이 핵심이었다. 

오랜만에 에라토스테네스의 체를 정리해보았다. 

https://sinclairstudio.tistory.com/492

에라토스테네스의 체 (소수판별 알고리즘) Python

from collections import deque
import sys

input = sys.stdin.readline

INF = 1000000
primes = [True] * (INF+1) # 소수
primes[0] = False # 자연수 아님
primes[1] = False # 소수 될 수 없음
for i in range(2, int(INF**0.5)+1):
    if primes[i]:
        for j in range(i*i, INF, i): # i 의 배수들을 지우기
            primes[j] = False

def bfs(n, a, b):
    count = 0
    queue = deque([])
    queue.append((n, 0))
    visited = [False] * (INF+1)
    visited[n] = True
    while queue:
        now, count = queue.popleft()
        if a <= now <= b and primes[now]:
            return count
        snap1 = now // 2
        snap2 = now // 3
        snap3 = now + 1
        snap4 = now - 1

        if 0 <= snap1 <= INF and not visited[snap1]:
            visited[snap1] = True
            queue.append((snap1, count+1))
        if 0 <= snap2 <= INF and not visited[snap2]:
            visited[snap2] = True
            queue.append((snap2, count+1))
        if 0 <= snap3 <= INF and not visited[snap3]:
            visited[snap3] = True
            queue.append((snap3, count+1))
        if 0 <= snap4 <= INF and not visited[snap4]:
            visited[snap4] = True
            queue.append((snap4, count+1))

    return -1




T = int(input())

for i in range(T):
    N, A, B = map(int, input().split())
    print(bfs(N, A, B))