백준 핑거스냅 17394번

문제

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

설명

• 문제를 전체적으로 풀면 간단하고 명시적으로 소수-> 에라체사용
• 그리고 1, 2, 3, 4번의 경우의 가짓수 -> q의 상태
• 조건에 맞는 소수면 출력 끝!

그러나 아주 큰 실수를했다- > 바보였다....

Eras() 함수에서 Prime[j] = 0;를 해야하는데 Prime[i] = 0으로 했다 아주 바보였다. ㅠㅠㅠㅠ

정답 소스

#include <bits/stdc++.h>

using namespace std;

int n, t, a, b, nx;
//소수의 범위는 2이상 10만이하 
int Prime[110000];
bool visited[1000001];
void init() {    
    for (int i = 1; i <= 100000; i++) Prime[i] = 1;
}

//prime[i] = 1이면 소수이다 
void Eras() {
    for (int i = 2; i <= 100000; i ++) {
        if (Prime[i] == 0) continue;

        for (int j = i + i; j <= 100000; j += i) {
            Prime[j] = 0;
        }
    }
}
int bfs() {

    queue<pair<int, int>> q;
    q.push({ n, 0 });
    memset(visited, 0, sizeof(visited));
    visited[n] = 1;

    while (!q.empty())
    {
        int now = q.front().first;
        int cnt = q.front().second;
        q.pop();
        //cout << now << " " << cnt << endl;
        if (now >= a && now <= b) {
            if (Prime[now] == 1) {
                return cnt;
            }
        }

        nx = now / 2;
        if (!visited[nx]) {
            q.push({ nx, cnt + 1 });
            visited[nx] = 1;
        }
        nx = now / 3;
        if (!visited[nx]) {
            q.push({ nx, cnt + 1 });
            visited[nx] = 1;
        }

        nx = now + 1;
        if (!visited[nx]) {
            q.push({ nx, cnt + 1 });
            visited[nx] = 1;
        }

        if (now > 2) {
            nx = now - 1;
            if (!visited[nx]) {
                q.push({ nx, cnt + 1 });
                visited[nx] = 1;
            }
        }
    }
    return -1;
}
int main() {

    cin >> t;
    init();
    Eras();
    while (t--)
    {
        cin >> n >> a >> b;
        cout << bfs() << endl;
    }
    return 0;
}