[JAVA]백준_9421_소수상근수

문제링크

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

9421번: 소수상근수

 

 

에라토스테네스의 체 를 사용하여 해결하였다.

소수를 판별하는 알고리즘 으로써 소수를 빠르게 구할 수 있다.

 

1. 소수를 판별한 범위만큼 배열 생성

2. 2부터 시작하여 특정 수의 배수에 해당하는 수를 모두 지운다. (지울 때 자기자신은 지우지 않음)

3. 2부터 시작하여 남아있는 수 출력

 

에라토스테네스의 체 코드

 

중간에 find를 사용하여 소수상근수를 판별하여 주었다.

1이 안되고 계속 돌면 소수상근수가 아니다..!

 

 

범위가 10000000 까지 주어져서 제곱근 중에 가장 큰 수는 999999로 만들어 진다고 생각하였다.

이렇게 하니 487이 만들어질 수 있는 가장 큰 수여서 boolean배열을 487만큼 할당하여 체크하여 주었다.

 

소수상근수 구하는 함수

number == 1이 되면 소수상근수이므로 true를 반환

무한루프에 도는 경우 (isChecked[num] == true 인 곳을 다시 방문하는 경우) false를 반환

 

다른 경우 제곱근을 구하기 위해 find(num)을 반환하였다.

 

package BOJ;

import java.io.*;
import java.util.Arrays;

//소수상근수
//https://www.acmicpc.net/problem/9421
public class Main_9421 {
    static int N;
    static boolean isChecked[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        primeNumber(N);
    }

    //에라토스테네스의 체
    static void primeNumber(int N) throws IOException {
        int[] arr = new int[N+1];

        //배열 생성해서 초기화
        for(int i=2;i<=N;i++) arr[i] = i;


        //2부터 시작해서 특정 수의 배수에 해당하는 수 모두 지우기
        //지울때 자기자신은 지우지 않고, 이미 지워진 수는 ㅌㅌ
        for(int i=2;i<=N;i++){
            if(arr[i] == 0) continue;

            for(int j=2*i;j<=N;j+=i){
                arr[j] = 0;
            }
        }

        //소수 출력
        for(int i=2;i<=N;i++){
            if(arr[i] !=0){
                //System.out.println(arr[i]);
                isChecked = new boolean[487];
                if(find(arr[i])) {
                    System.out.println(arr[i]);
                }
            }
        }
    }

    private static boolean find(int number) {
        //소수상근수 구하기
        //양의 정수 n의 각 자리수의 제곱의 합을 계산한다. 그렇게 해서 나온 합도 각 자리수의 제곱의 합을 계산한다.
        // 이렇게 반복해서 1이 나온다면, n을 상근수라고 한다.
        if(number == 1){
            return true;
        }


        int num = 0;
        String str = Integer.toString(number);
        for(int i=0,size = str.length();i<size;i++){
            num += Math.round(Math.pow(str.charAt(i)-'0',2));
        }

        if(isChecked[num]) return  false;
        else isChecked[num] = true;

        return find(num);
    }
}