[백준 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");
}
}
}