[BOJ] 9421 - Happy Prime Number

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

---

[알고리즘풀이]

1 ~ N 까지의 Prime 중 Happy Number를 만족하는 수를 찾아서 출력해야 한다.

 

-1) 소수 찾기

1 ~ N 까지의 Prime을 먼저 찾아야 되므로 에라토스테네스 체를 이용한다.

#define size 1000001
bool p[size];

	long long i, j;
	for (i = 2; i < size; i++) {
		if (p[i] == false) {
			for (j = (i * i); j < size; j += i)
				p[j] = true;
		}
	}

-2) Happy Number 찾기

숫자 N에 대해 각 자릿수의 제곱을 더해가는 과정을 반복하다,

1이 되면 Happy Number이고, 1이 나오지 않고 Cycle에 갇힌다면 Un Happy Number이다.

따라서 우리는 각 자릿수의 제곱을 더해가는 과정을 반복하며, Cycle을 체크해줘야 된다.

이때, N의 다음 happy number는 모든 자릿값이 9일 때 최대를 갖는다. 또, N이 10^6보다 작거나 같으므로

Happy Number를 구해가는 과정에서 가장 큰 값은 81 * 6인 486을 넘어갈 수 없다.

따라서, bool 배열인 c 배열을 만들어줘서, 그동안 구해온 수들을 check 해주고 같은 수가 나오면 Cycle이 생겼다고 판단하면 된다.

#include<iostream>
#include<cmath>

using namespace std;

#define size 1000001

bool p[size];
bool c[487];

int get_happynumber(int p) {
	int next = 0, l;
	for(l = 1; ; l++)
		if ((int)pow(10, l - 1) <= p && p < (int)pow(10, l)) {
			break;
		}
	int end = l;
	for (int j = 0; j < end; j++) {
		int temp = (p % (int)pow(10, l)) / (int)pow(10, l - 1);
		next += temp * temp;
		l--;
	}
	return next;
}

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

	long long i, j;
	for (i = 2; i < size; i++) {
		if (p[i] == false) {
			for (j = (i * i); j < size; j += i)
				p[j] = true;
		}
	}
	int n;
	cin >> n;
	for (int i = 2; i <= n; i++) {
		int prime = i;
		if (p[i] == false) {
			for (int j = 0; j < 487; j++)
				c[j] = false;
			while (1) {
				int next = get_happynumber(prime);
				if (next == 1) {
					cout << i << '\n';
					break;
				}
				else if (c[next] == true) {
					break;
				}
				else {
					c[next] = true;
				}
				prime = next;
			}
		}
	}
}

---