백준 9421번 소수상근수

문제

양의 정수 n의 각 자리수의 제곱의 합을 계산한다. 그렇게 해서 나온 합도 각 자리수의 제곱의 합을 계산한다. 이렇게 반복해서 1이 나온다면, n을 상근수라고 한다.

700은 상근수이다.

• 72 + 02 + 02 = 49
• 42 + 92 = 97
• 92 + 72 = 130
• 12 + 32 + 02 = 10
• 12 + 02 = 1

2는 상근수가 아니다.

• 22 = 4
• 42 = 16
• 12 + 62 = 37
• 32 + 72 = 58
• 52 + 82 = 89
• 82 + 92 = 145
• 12 + 42 + 52 = 42
• 42 + 22 = 20
• 22 + 02 = 4
• 42 = 16
• ... 끝나지 않는다

소수는 1과 자기자신을 제외하고 약수가 없는 수이다. 2, 3, 5, 7, 11, 13, 17, 19, ... 는 소수이다.

소수상근수는 소수이면서 상근수인 숫자이다. 7, 13, 19, ... 는 소수 상근수이다.

n이 주어졌을 때, n보다 작거나 같은 모든 소수상근수를 구하는 프로그램을 작성하시오.

문제풀이

(1) 생각

 문제에 주어진 대로 각 자리수를 제곱하여 더하는걸 1이 될 때 까지 반복할 것입니다.
 이 과정 중, 반복되는 숫자가 나오면, 루프가 발생한 것이므로 해당 루프의 수들은 소수 상근수가 될 수 없습니다.
 문제 예시로 보면, 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 의 반복이 됩니다.
 따라서 4 이후 다시 16 -> 37 -> ... 이 반복 될 것이 자명하므로 이 루프 안의 8개의 수 4, 16, 37, 58, 89, 145, 42, 20 은 모두 소수 상근수를 만들 수 없게됩니다.

(2) 코드 8~9

 위 생각에 따라, 각 자리수 제곱합을 반복하는 과정에서 나오는 수들이, 소수 상근수를 만들 수 있는지, 없는지 여부를 기억하는 행렬을 만들어줍니다.

(3) 코드 39~47

 에라테네스의 체로 입력된 N 이하의 소수를 구하면서, 각 소수들이 소수상근수인지 판단해줍니다.

(4) 코드 10~34

 소수상근수 인지 판단해주는 함수를 만들어줍니다.
 각 자리수 제곱의 합이 1이 나오거나, 반복될 때까지 재귀적으로 반복하고, 각 과정의 수들을 set으로 저장해줍니다.
 과정이 끝나고, set에 저장한 과정들의 수들을 각각 소수상근수가 될 수 있는지, 없는지에 따라 (2)에 만들어 놓은 행렬에 저장합니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 1000000;
	int N;
	bool used[MAX + 11];
	bool YES[MAX + 11]; // Yes[x] : x가 소수상근수인 숫자
	bool NO[MAX + 11]; // No[x] : x가 소수상근수인 숫자
	bool OK(int n, set<int> S) {
	// 이미 방문했던 숫자
	if (NO[n]) return false;
	if (YES[n]) return true;
	// 반복되는 순간 false
	if (S.count(n)) {
	for (auto num : S) NO[num] = true; // 기억
	return false;
	}
	S.insert(n);
	// 각 자리수 제곱의 합 계산
	int temp = 0;
	while (n) {
	temp += (n % 10) * (n % 10);
	n /= 10;
	}
	// set에 모아놨던거 다 true
	if (temp == 1) {
	for (auto num : S) YES[num] = true;
	return true;
	}
	else if (OK(temp, S)) return true;
	return false;
	}
	int main() {
	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	// 소수를 구하면서 해당 소수가 소수상근수인지 판단.
	for (int i = 2; i <= N; ++i) {
	if (used[i]) continue;
	set<int> ST; // 반복되는지 여부를 set 으로 판단
	if (OK(i, ST)) cout << i << '\n';
	for (int j = i + i; j <= N; j += i)
	used[j] = true;
	}
	return 0;
	}

view raw BOJ 9421.cpp hosted with ❤ by GitHub