백준 17394 핑거 스냅

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

숭고한 공식 풀이는 여기서 보실 수 있습니다.

탐색 문제입니다. 에라토스테네스의 체를 이용하여 소수 판별 여부를 저장하는 배열을 하나 만들어 두고 구간 안에 있는 소수가 나올 때까지 bfs를 돌리면 됩니다.

#include<bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
const int SZ=100005;
int np[SZ];
int vst[40*SZ];
void era(){
	for(int i=2;i*i<=SZ;i++){
		if(np[i]==1) continue;
		for(int j=i*i;j<SZ;j+=i){
			np[j]=1;
		}
	}
}
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int t; cin>>t;
	era();
	while(t--){
		memset(vst,0,sizeof(vst));
		int x,l,r; cin>>x>>l>>r;
		queue<pair<int,int>> q;
		q.push({x,0}); vst[x]=1;
		bool flg=true;
		while(!q.empty()){
			auto f=q.front(); q.pop();
			if(l<=f.ff && f.ff<=r && np[f.ff]==0){
				cout<<f.ss<<'\n';
				flg=false;
				break;
			}
			if(vst[f.ff/2]==0){
				vst[f.ff/2]=1;
				q.push({f.ff/2,f.ss+1});
			}
			if(vst[f.ff/3]==0){
				vst[f.ff/3]=1;
				q.push({f.ff/3,f.ss+1});
			}			
			if(f.ff+1<4*SZ && vst[f.ff+1]==0){
				vst[f.ff+1]=1;
				q.push({f.ff+1,f.ss+1});
			}
			if(f.ff-1>=0 && vst[f.ff-1]==0){
				vst[f.ff-1]=1;
				q.push({f.ff-1,f.ss+1});
			}						
		}
		if(flg) cout<<-1<<'\n';
	}
	return 0;
}