[백준] 9421번 소수상근수 (C++)

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

 

 

이 문제는 2부터 n 까지의 소수를 구한뒤 n이 입력되었을때 n보다 작은 소수가 각 자리의 수를 제곱해서 더한 값이 1이 나올 경우 그 값을 출력하는 문제이다.

 

우리가 먼저 해결해야할 것은 2부터 N까지의 소수를 판별하는 일이다.

이후 순차적으로 탐색하여 소수가 아닌 것은 각 자리 수를 제곱해서 더한 뒤 그 값을 방문처리 하며 방문했던 값이 나온 경우

계속해서 그 값이 반복되기 때문에 제곱했을때 1이 나올 수 없다는 의미이며 건너뛰는 것을 구현하면 된다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N;
bool arr[1000001];       // 소수이면 false

void Init() {
    arr[0] = true;
    arr[1] = true;

    for(int i = 2; i <= 1000000; i++) {
        if(!arr[i]) {
            for(int j = i + i; j <= 1000000; j += i) {
                arr[j] = true;
            }
        }
    }
}

void check(int a) {
    set<int> st;

    int answer = a;

    while(true) {
        if(st.find(a) != st.end()) {
            return;
        }
        else st.insert(a);
        string s = to_string(a);

        int total = 0;
        for(int i = 0; i < s.size(); i++) {
            int tmp = s[i] - '0';
            total += tmp * tmp;
        }

        a = total;

        if(total == 1) {
            cout << answer << endl;
            return;
        }
    }
}

void solve() {
    Init();

    for(int i = 2; i <= N; i++) {
        if(!arr[i]) {
            check(i);
        }
    }
}


void input() {
    cin >> N;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

에라토스테네스의 체를 사용하여 소수를 미리 다 판별한 후 set을 사용하여 방문처리를 수행하여 제곱했을 때 1인지 판별하였다.