[C++] 백준 9420번: 소수상근수

문제 링크

9420번: 소수상근수

문제 요약

어떤 수의 각 자릿수의 제곱 수를 더해서 나온 수를 구하는 과정을 반복했을 때, 1이 되면 이 수를 상근수라고 한다. N이 주어지면 N 이하의 소수인 상근수를 모두 구해야 한다.

접근 방법

에라토스테네스의 체를 이용해서 전처리로 소수를 모두 구해줍니다.

그리고 N 이하의 소수들에 대해서 상근수를 구해주면 됩니다. 각 자릿수를 제곱해서 더해서 수를 새로이 구하고, 그 수에 대해서도 같은 절차를 반복해주면 됩니다. 단, 1에 영영 도달하지 않을 수도 있습니다. 이를 막기 위해서 unordered_set에 이 절차에서 나오는 수들을 저장해줍니다. 만약 셋 내에 있는 수가 다시 나오게 된다면 이 수는 소수상근수가 아니게 됩니다.

만약 1에 도달하게 되면 소수상근수에 해당하기 때문에, 해당 수를 출력해주고 다음 소수로 건너가면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1000001;
bool visited[MAX];

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

	int n;
	cin >> n;

	for (int i = 2; i <= ceil(sqrt(n)); i++)
		if (!visited[i])
			for (int j = i * 2; j <= n; j += i)
				visited[j] = true;

	for (int i = 2; i <= n; i++) {
		if (!visited[i]) {
			unordered_set<int> s;

			int num = i;
			bool flag = false;
			while (1) {
				if (num == 1)
					break;

				if (s.find(num) != s.end()) {
					flag = true;
					break;
				}

				s.insert(num);

				string tmp = to_string(num);
				num = 0;

				for (auto& j : tmp)
					num += pow(j - '0', 2);	
			}

			if (!flag)
				cout << i << '\n';
		}
	}

	return 0;
}