<Algorithm> 6. 2023번 신기한 소수

2023번 신기한 소수

• input에 1~8까지 숫자가 입력되면 자리수로 판단하여 자리수에 해당하는 소수를 모두 찾는 문제 ex) 2-> 23 31 37 ~~ 79

• 주의할점 예를들어 21 경우 이미 소수가 아니므로 나머지 자리수를 판단할 필요가 없다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

import java.io.BufferedReader; import java.io.InputStreamReader;   public class Main {     public static void main(String[] args) throws Exception {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                 int T = Integer.parseInt(br.readLine());           String[] array={"2","3","5","7"}; // 소수         int N=T; // 최대깊이         int dep=0; //현재깊이         Check c=new Check(N);                   for(int i=0;i<array.length;i++){                 c.prim(array[i],dep); //2 3 5 7 한번 반복         }      }          public static boolean check(String num){// 소수판별         int input=Integer.parseInt(num);          int sqrt= (int) Math.round(Math.sqrt(input));               for(int i=2;i<=sqrt;i++){ // 제곱근해서 반올림 값 같거나 작을떄 까지               if(input%i==0){                  return false;              }          }         return true;             } } class Check{ // 출력 & dfs     String[] array;     int N;          public Check(int N) {         // TODO Auto-generated constructor stub         this.N=N;     }          public void prim(String nums,int dep){         dep++; // 깊이 증가         if(dep==N&&Main.check(nums)){ // 깊이가 마지막이고 소수일경우             System.out.println(nums);// 출력         }else{             for(int i=0;i<10;i++){  // 0~9까지의 수 판단                 if(Main.check(nums)){  // 들어온 수가 소수가 아니면 더이상 탐색안함                    prim(nums+""+i,dep); // 소수일경우 dps                 }             }                             }     } } Colored by Color Scripter

cs

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