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

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

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

입력

첫째 줄에 n (10 ≤ n ≤ 1000000)이 주어진다.

 

풀이

n까지의 모든 수들이 true인 배열을 하나 만든다.

에라토스테네스로 소수가 아닌 애들을 false로 걸러낸다

문제에 나온 그대로 구현해서 상근수가 아닌 경우도 false로 걸러낸다

 

상근수 판별 :

각 자리 숫자의 제곱을 더한 값들을 연속적으로 구하면서 한번이라도 구했던 값이 나오면 지금까지 나왔던 값들은 전부 false처리한다

(어차피 순환할게 뻔하기 때문)

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

const int INF = 1000001;

vector<bool> isSoSang(INF, true);

// 각 자리 숫자 제곱 더하는 함수
int sumOfDigit(int num) {
    int sum = 0;
    while(num>0) {
        sum += (num%10)*(num%10);
        num/=10;
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    
    // 소수 판별
    isSoSang[0] = isSoSang[1] = false;
    for(int i=2; i<=sqrt(n); i++) {
        if(!isSoSang[i])
            continue;
        for(int j=i*i; j<=n; j+=i)
            isSoSang[j] = false;
    }
    
    // 소수상근수 판별
    for(int i=2; i<=n; i++) {
        if(!isSoSang[i]) // 소수 아니면 살펴볼 필요도 없이 넘어간다
            continue;
        int tmp = i;
        vector<int> history;
        while(true) {
            if(tmp == 1) {
                // 앗! 1이 나왔다!
                break;
            }
            if(count(history.begin(), history.end(), tmp) != 0) { 
                // 앗! 순환이 발견되었다!
                for(int j : history) // 나왔던 애들 전부 상근수 제외
                    isSoSang[j] = false;
                break;
            }
            history.push_back(tmp);
            tmp = sumOfDigit(tmp);
        }
    }
    
    // 출력
    for(int i=2; i<=n; i++) {
        if(isSoSang[i])
            cout << i << "\n";
    }
    
    return 0;
}