[백준OJ] 9421번 소수상근수

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

9421번: 소수상근수

---

 

풀이

먼저, N이하의 소수판별은 에라토스테네스의 체 알고리즘을 이용해서 소수를 판별했다.

https://khu98.tistory.com/227

[알고리즘] 소수판별 알고리즘 C++

 

소수를 판별해나가면서, 해당 소수가 소수상근수인지 판별을 하는데, 해당숫자를 과정을 통과하다가 이전에 만났던 수를 만난다면, 무한루프를 돌고있다는 뜻이므로 소수상근수가 되지 못한다.

예를들어 문제에 나온 2를 예를들면,

2*2=4

4*4=16

1*1+6*6=37

3*3+7*7=58

5*5+8*8=89

8*8+9*9=145

1*1+4*4+5*5=42

4*4+2*2=20

2*2+0*0=4

4*4=16

1*1+6*6=37

.....

로 무한 반복을 돌기 때문에, 두번째 4*4=16에서 이미 소수상근수가 되지 못한다는것을 판별할 수 있다.

2는 소수상근수가 되지못한다는것을 알았는데, 다음소수들도 이처럼 하나하나 검사를 해야할까?

아니다. 해당 소수가 소수상근수가 되지 못하면, 해당소수를 소수상근수로 만드는 과정에서 만난 모든 수들은 결과적으로 소수상근수가 되지 못한다.

예를들어 어떤 수를 소수상근수로 만드는 과정에서 중간에 89가 튀어나왔다고 하자. 그럼 8*8+9*9=145 , 처럼 위의 무한루프에 끼어들기때문에, 소수상근수가 아닌 수가 지나왔던 모든 수들을 만나면 소수상근수를 만들지 못한다.

 

반대로 해당 소수가 소수상근수라면, 해당 소수를 소수상근수로 만드는 과정에서 만난 모든 수들은 결과적으로 소수상근수가 될 수 있다.

 

따라서 소수상근수가 될 수 있는 숫자의 배열과, 소수상근수가 될 수 없는 숫자의 배열을 선언해둔뒤,

해당 소수가 소수상근수라면, 소수상근수가 될 수 있는 숫자의 배열에 지금까지 지나왔던 모든 수들을 체크해주고, 

해당 소수가 소수상근수가 아니라면, 소수상근수가 될 수 없는 숫자의 배열에 지금까지 지나왔던 모든 수들을 체크해준다.

 

그런뒤, 다음 소수를 체크할때, 위의 두 배열에 저장된 숫자중 하나를 만난다면, 바로 판별할 수 있기에 경우에 따라 true / false를 리턴해주면된다.

반응형

코드

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;

bool is_prime[1000001] = { 0 };
bool is_ok[1000001] = { 0 };
bool is_false[1000001] = { 0 };
map<int,bool> visited;
bool sogen(int n) {
	while (n != 1) {
		if (is_ok[n]) {
			return true;
		}
		if (is_false[n]) {
			return false;
		}
		if (visited[n]) {
			for (auto k : visited) {
				is_false[k.first] =true;
			}
			return false;
		}
		visited[n] = true;
		int total = 0;
		while (n) {
			total += ((n % 10)*(n % 10));
			n /= 10;
		}
		n = total;
	}
	for (auto k : visited) {
		is_ok[k.first] = true;
	}
	return true;
}

void solve(int n) {
	for (int i = 2; i <= n; i++) is_prime[i] = true;

	for (int i = 2; i <= n; i++) {
		if (is_prime[i]) {
			visited.clear();
			if (sogen(i)) {
				cout << i << "\n";
			}
			for (int j = i + i; j <= n; j += i) {
				is_prime[j] = false;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int n;
	cin >> n;
	solve(n);
	return 0;
}