#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보다 작거나 같은 모든 소수상근수를 구하는 프로그램을 작성하시오.

• 코드

#include <iostream>
#include <vector>
#include <set>

using namespace std;

void isPrime(int n, vector<bool>& is_prime){
	is_prime[0] = is_prime[1] = false;

	for (int i = 2; i * i <= n; i++) {
		if (is_prime[i]) {
			for (int j = i * i; j <= n; j += i) {
				is_prime[j] = false;
			}
		}
	}
}

void isSanggeun(int n, vector<bool>& is_prime) {
	is_prime[2] = is_prime[3] = is_prime[5] = false; // 초반 상근수가 아닌 것들 지우기

	for (int i = 7; i <= n; i++) {
		if (is_prime[i]) { //소수이면 상근수인지 확인
			set <int> s; //상근수 계산결과를 저장할 set
			int num = i; //계산할 값
			while (true) {
				int sum = 0; //계산 결과
				while (true) { // 한 자릿수씩 계산해서 더하기 
					sum += ((num % 10) * (num % 10));
					if (num >= 10) {
						num /= 10;
					}
					else {
						break;
					}
				}
				if (s.find(sum) != s.end()) { // 이미 한 번 계산한 결과라면 
					is_prime[i] = false;
					break;
				}
				else if (sum == 1) {
					break;
				}
				else {
					s.insert(sum);
					num = sum; //num 갱신
				}
			}

		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	vector<bool>is_prime;

	//입력
	cin >> n;

	//연산
	//미리 n까지의 소수 구하기
	is_prime.assign(n + 1, true);
	isPrime(n, is_prime);
	//n까지의 소수 상근수 구하기
	isSanggeun(n, is_prime);

	//출력
	for (int i = 7; i <= n; i++) {
		if (is_prime[i]) {
			cout << i << "\n";
		}
	}
	

}

• 해설

1. isPrime 함수

- 에라토스테네스의 체를 이용하여 n까지의 소수를 구하는 함수

 

2. isSanggeun 함수

- 소수상근수를 구하는 함수

- 연산을 반복하다가 같은 결과가 나오면 그때부터는 소수상근수에 해당하지 않음

: 먼저 초반 상근수가 아닌 것들 false로 지우기

: 7부터 n까지 소수이면 상근수인지 확인

: sum에 첫째 자리부터 제곱해서 저장

: num이 10보다 크거나 같으면 10으로 나눈 뒤 반복, 만약 이제 10보다 작으면 한 자리씩 계산을 완료한 것이므로 break

: 이후 set에 이미 sum이 존재하면 소수 상근수가 아니므로 i를 false로 지운 뒤 break

: 만약 sum이 1이라면 소수 상근수이므로 그냥 break

: 만약 위 두가지 모두에 해당하지 않는다면 계속 계산해야하므로 sum을 s에 넣고 num에 sum을 대입해 다시 연산 반복

 

3. main 함수

: isPrime 함수를 통해 n까지 소수 모두 구하기

: isSanggeum 함수를 통해 n까지 소수 상근수 모두 구하기