[백준 10434] 행복한 소수 - 소수 구하기 + 행복한 수

행복한 수에 대한 연습문제를 풀다가, 백준에 관련된 문제가 있나 싶어 찾아보았습니다.

행복한 수만 구하는 문제는 아니고, 행복한 소수를 구하는 문제가 있었어요.

그래서 한 번 개념 정리를 먼저 하고 문제를 풀어보고 정리를 하려 합니다.

 

|  행복한 수란?

십진수의 수가 있을 때, 예를 들어 14가 있다고 할 때, 

각 자릿수를 제곱한 합은 1^2 + 4^2 = 18 입니다.

다시 29의 각 자릿수를 제곱한 합을 구하면 1^2 + 8^2 = 65

이 과정을 계속하다보면, 64,37,58,89,145,42,20,4,16,37,58,89,145,42.... 이 나오게 되는데요.

 

- 어떤 수는 14처럼 '1이 아닌 중복되는 수'를 지점으로 무한히 동일한 수열이 반복되는 반면,

- 어떤 수는 제곱합의 끝이 1이 되면서 이후에는 1이 반복되어 나옵니다.

 

'행복한 수'는 이처럼 제곱합의 끝이 1이 나오는 수를 이야기합니다.

 

[ 행복한 수를 찾는 코드 ]

public static boolean isHappy(int n) {

        // 중복된 지점부터는 저장X
        HashSet<Integer> set = new HashSet<>();

        while (set.add(n)) { //set이 이미 해당 값을 가지고 있을 때 false --> 루프탈출
            // 각 자릿수의 제곱합
            int sum = 0;
            while (n > 0) {
                sum += (int) Math.pow(n % 10, 2);
                n /= 10;
            }

			// 합이 1이 나오면 행복한 수, 아니면 set에 add하고 중복수 있는지 확인
            if (sum == 1) {
                return true;
            } else {
                n = sum;
            }
        }

        return false;
    }

 

|  소수 구하기

소수는 자연수 N을 1부터 N까지 나누었을 때 나누어떨어지는 수가 오직 1과 자기자신 뿐인 수를 말합니다.

단순 구현을 하게 되면 아래와 같이 풀 수 있는데요

// 방법1. 2부터 N - 1까지 루프를 돌려 n을 나누어 본다.
public static boolean isPrimeNumber(int n) {

    for (int i = 2; i <= n - 1; i++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

아래의 두가지 원리를 이용해서 위를 개선하면 아래와 같았어요.

(1) 2가 아닌 짝수는 절대 소수일 수가 없다는 점 - ex. 4, 6, 8, 10.. 모두 2로 나누어떨어지죠 (2) 홀수 N을 짝수인 수로 나누면 나누어떨어지지 않는다는 점 - ex. N이 125일 때, 나누어떨어지는 수는 1, 5, 125       > 이는 짝수인 수의 구구단을 생각하면 쉬웠어요.        > 예를 들어, 4의 구구단은 4x1 = 4, 4 x 2= 8, 4 x 3 = 12.... 모두 짝수가 나와요.       > 결국 짝수인 수를 다른 자연수로 곱해봤자 절대 홀수가 나올 수 없다는 의미이죠.

// 방법2. 수학적 원리 사용 - 2가 아닌 짝수는 소수가 아님
public static boolean isPrimeNumber2(int n) {

    // 2가 아닌 짝수 여부
    if (n != 2 && n % 2 == 0) { 
        return false;
    }

    // 3부터 홀수로만 나누어본다.
    for (int i = 3; i <= n - 1; i+=2) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

 

🛎 10434 행복한 소수

|  문제 

Q. : 아래의 수열에서 다음에 올 수를 찾으시오.

313 331 367 ...

경복 : ??

강산 : 379.

경복 : 뭐?

강산 : 행복한 소수잖아.

경복 : 행복한 뭐?

강산 : 그러니까, 자리수의 제곱의 합을 구하는 연산을 계속 반복했을 때 1이 되는 수를 행복한 수라고 하잖아. 행복한 소수는 그 중 소수인 수이고.

7은 분명 소수이다. 과연 행복할까?

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

7은 행복한 수이다 ☺.

사실 7은 행복한 소수 중 가장 작은 수이다. (이 문제에서는 1을 소수가 아닌 것으로 생각한다)

어떤 수가 주어지면 이 수가 행복한 소수인지 판정해보자.

|  입력

첫 줄에 테스트 케이스의 수 P가 주어진다. (1 ≤ P ≤ 1000)

각 테스트 케이스는 테스트 케이스 번호와 행복한 소수인지 판정해야 할 정수인 M으로 이루어져 있다. (1 ≤ m ≤ 10000).

|  출력

각 테스트 케이스마다, 테스트 케이스의 번호, 입력받은 수, 만일 M이 행복한 소수라면 YES 아니라면 NO를 공백으로 각각 구분하여 출력한다.

|  예제 입력

4
1 1
2 7
3 383
4 1000

|  예제 출력

1 1 NO
2 7 YES
3 383 YES
4 1000 NO

 

⌨️ 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Ex10434 {

	// 1단계 메서드 : 소수 확인 (단, 1은 소수가 아니다)
    public static boolean isPrimeNumber(int n) {

        // 탈출문1 : 1은 소수X
        if (n == 1) {
            return false;
        }

        // 탈출문2 : 2가 아닌 짝수는 소수x
        if (n != 2 && n % 2 == 0) {
            return false;
        }

        // 3 ~ N 까지 홀수로 나누어떨어지지 않는지 확인 
        for (int i = 3; i <= n - 1; i+=2) {
            if (n % i == 0) {
                return false;
            }
        }

        return true;
    }

	// 2단계 메서드 : 행복한 수 확인
    public static boolean isHappy(int n) {

        // 중복수 확인용 set
        HashSet<Integer> set = new HashSet<>();

        while (set.add(n)) { 
            // 각 자릿수의 제곱합이
            int sum = 0;
            while (n > 0) {
                sum += (int) Math.pow(n % 10, 2);
                n /= 10;
            }

            if (sum == 1) {
            	// 1이면 행복한 수
                return true;
            } else {
            	// 아니면
                n = sum;
            }
        }

		// 중복수가 나온 경우
        return false;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int P = Integer.parseInt(br.readLine()); // 케이스 수
        int[] allCase = new int[P];

        // 모든 케이스 입력
        while (P > 0) {
            st = new StringTokenizer(br.readLine());
            int idx = Integer.parseInt(st.nextToken()) - 1;
            int num = Integer.parseInt(st.nextToken());

            allCase[idx] = num;

            P--;
        }

        // 각 케이스별 행복한 소수여부 확인
        for (int i = 0; i < allCase.length; i++) {

            System.out.printf("%d %d ", i + 1, allCase[i]);

            if (!isPrimeNumber(allCase[i])){
                System.out.print("NO\n");
                continue;
            }

            if (!isHappy(allCase[i])) {
                System.out.print("NO\n");
                continue;
            }

            System.out.print("YES\n");

        }

    }
}