[백준] 알고리즘 분류(수학,JAVA)2023번, 신기한 소수

문제 링크

2023번: 신기한 소수

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 수빈이는 관심있는 소수는 왼쪽부터 1, 2, 3, 4자리 모두 소수인 값입니다.

2. N자리 수 중에 관심있는 소수들을 결과로 출력합니다.

3. 결과를 출력할 때에는 오름차순으로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. N자리의 수를 만들면서 관심있는 소수 조건에 만족하는 소수를 탐색합니다.

 

3. 탐색이 끝나고 얻은 관심있는 소수들을 결과로 출력합니다.

 

소수 조건 확인!

 

이 문제에 메모리 제한은 4MB입니다.

 

메모리 제한으로 인하여 소수를 구하는 방법인 에라토스테네스의 체를 사용하여 먼저 소수를 판정할 수 없습니다.

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

소수 판정

 

N자리의 수가 될 수 있는 값들이 왼쪽부터 1, 2, 3, 4자리가 소수인지 판단해야 합니다.

 

소수를 판단할 때에는 해당 값의 "2 ≤ n ≤ 제곱근" 값으로 나누어 떨어지면 소수가 아님을 판정할 수 있습니다.

 

N자리의 수가 될 수 있는 값

 

N자리의 시작값 : {2, 3, 5, 7}만 가능합니다.

 

Why? : 1자리가 소수일 때를 확인하는데 1의 자리에서 소수인 값은 {2, 3, 5, 7}만 존재하기 때문입니다.

 

다음 자리의 올 수 있는 값 : {1, 3, 5, 7, 9}만 가능합니다.

 

Why? : 1의 자리 이후에, 짝수가 오게되면 항상 2으로 나누어떨어지기 때문에 소수가 아니게 됨으로 홀수만 들어올 수 있습니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 3

 

2. N자리의 수를 만들면서 관심있는 소수 조건에 만족하는 소수를 탐색합니다.

 

시작값 기준 탐색 시작!

2~

3~

5~

7~

 

다음 자릿수 채우기!

다음 가능한 자릿수 {1, 3, 5, 7, 9}

 

21~ : 3으로 나누어 떨어짐 ▶ 소수 X

23~ : √23이하의 값으로 나누어 떨어지지 않음 ▶ 소수 O

25~ : 5으로 나누어 떨어짐 ▶ 소수 X

27~ : 3으로 나누어 떨어짐 ▶ 소수 X

29~ : √29이하의 값으로 나누어 떨어지지 않음 ▶ 소수 O

 

31~ : √31이하의 값으로 나누어 떨어지지 않음 ▶ 소수 O

33~ : 3으로 나누어 떨어짐 ▶ 소수 X

35~ : 5으로 나누어 떨어짐 ▶ 소수 X

37~ : √37이하의 값으로 나누어 떨어지지 않음 ▶ 소수 O

39~ : 3으로 나누어 떨어짐 ▶ 소수 X

 

.....

 

2333

2339

2393

...

7333

7393

 

3. 탐색이 끝나고 얻은 관심있는 소수들을 결과로 출력합니다.

 

2333

2339

2393

...

7333

7393

결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 1의 자리 올 수 있는 값과 다음에 올 수있는 홀수 값들을 미리 배열에 저장합니다.
• search함수를 이용하여 N자리의 관심있는 소수를 탐색합니다.
• 탐색으로 얻은 관심있는 소수들을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 N자리의 관심있는 소수를 탐색을 진행합니다.
• isPrime함수는 제곱근 이하의 값들을 나누어보면서 소수인지 확인합니다.

 

결과코드

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
	static int N;
	static int[] start = {2, 3, 5, 7};	//1의 자리 시작 할 수 있는 값 배열
	static int[] num = {1, 3, 5, 7, 9};	//1의 자리 이후 다음 올 수 있는 홀수들
	static StringBuilder answer = new StringBuilder();
	public static void main(String[] args) throws IOException{
		//입력값 처리하는 BufferedReader
        	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//결과값 출력하는 BufferedWriter
        	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());
		//각 N자리가 {2, 3, 5, 7}로 시작할 때 탐색!
        	for(int i=0;i<start.length;i++)
			search(1, start[i]);
		bw.write(answer.toString());	//관심있는 소수들 BufferedWriter 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//N의 자리를 소수인지 판별해 나아가며 탐색하는 함수
	static void search(int idx, int value) {
			if(primeCheck(value))	//소수인지 확인
			return;	//소수가 아닐 때 Return
		
		//관심있는 소수  완성!
        	if(idx == N) {
			answer.append(value).append("\n");
			return;
		}
        	//홀수 값들 추가해나아가며 탐색
		for(int i=0;i<num.length;i++) 
			search(idx+1, value * 10 + num[i]);
	}
    	//√제곱근 이하의 값으로 나누어 떨어지는지 확인하여 소수인지 파악하는 함수!
	static boolean primeCheck(int n) {
		for(int i=2;i<=Math.sqrt(n);i++) 
			if(n%i == 0)
				return true;
		return false;
	}
}