[JAVA]백준_2023_신기한 소수

문제링크

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

2023번: 신기한 소수

 

 

 

import java.util.Scanner;

public class Main {

	static int N;
	static int startNum;
	static int endNum;
	static int isPrime;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();

		StringBuilder sb = new StringBuilder();
		sb.append(1);
		for(int i=1;i<N;i++) sb.append(0);
		startNum = Integer.parseInt(sb.toString());
		
		sb = new StringBuilder();
		for(int i=0;i<N;i++) sb.append(9);
		endNum = Integer.parseInt(sb.toString());

		//N자리 숫자/(10*N)
		//N자리 숫자/(10*N-1)
		//N자리 숫자/(10*N-2)
		//N자리 숫자/(10*N-3) ..->N-(N-1)까지 자리수 구하면서 그 자리수가 다 소수인지 확인
		
		//dfs로 하나씩 넣으면서 소수인지 아닌지 구하기?
		
		int divideNum = 1;
		for(int i=N-1;i>=1;i--) divideNum*=10;
		for(int i=startNum;i<=endNum;i++) {
			isPrime = 0;
			dfs(i,N-1);
			if(isPrime == N) System.out.println(i);
		} //시간 초과

	}
	
	static void dfs(int num,int N) {
		int divideNum = 1;
		for(int i=N;i>=1;i--) divideNum*=10;
		
		int findNum = num / divideNum; //이 숫자가 소수인지 아닌지 찾아야함

		boolean isTrue = true;
		if(findNum == 0 || findNum ==1) return;
		
		//만약 끝자리가 2,4,6,8,0으로 끝나도 소수 x
		if(findNum!=2 && (findNum%10) %2 ==0) return;
		for(int i=2;i<=Math.sqrt(findNum);i++) { 
			if(findNum % i ==0) return;
		}
		
		if(isTrue) isPrime++;
		
		if(N>0) dfs(num,N-1); //1일때 까지 돌려주기

	}
	
}

 

4자리 수가 1234이면 1, 12, 123, 1234 4가지 경우를 소수인지 아닌지 체크해야한다.

그래서 dfs를 사용하여 N가지 경우의 수가 소수인지 아닌지 확인을 했다.

처음에는 Math.sqrt()까지 돌리면서 소수인지 아닌지 확인을 했다. 답은 나왔으나 8자리의 숫자의 경우 시간초과가 나는 문제점이 있었다.

그래서 소수를 구하는 알고리즘을 검색해보았는데 에라토스테네스의 해라는 알고리즘이 있었다.

근데 이 알고리즘은 2의 배수빼고 3의 배수빼고 ... 이런 식으로 진행하는 것이라서 시간초과 문제를 해결해 줄 수 없을 것 같았다.

그래서 생각해본 결과 내 코드에서는 N자리 숫자일 경우 1자리 숫자인 경우부터 소수인지 아닌지 체크를 하는데 어짜피 마지막 숫자가 2,4,6,8,0으로 끝나면 2의 배수이므로 굳이 소수인지 아닌지를 체크할 필요가 없을 것 같았다.

그래서 끝자리가 2,4,6,8,0인 경우를 제외하고 풀었다.

근데 만약에 한자리 숫자만 체크하는 경우 일때는 2는 소수이므로 2인 경우는 제외해주었다.