[백준] 5636번. 소수 부분 문자열(JAVA)

문제

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

---

풀이(17분)

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

public class Main {

    static boolean[] isPrime = new boolean[100001];
    static List<Integer> primeList = new ArrayList<>();

    public static void isPrime(){ // 100,000까지의 소수 먼저 확인
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;

        for(long i = 2; i < 100001; i++){
            if(isPrime[(int)i]){
                primeList.add((int)i);
                for(long j = i * i; j < 100001; j += i){
                    isPrime[(int)j] = false;
                }
            }
        }
        Collections.sort(primeList, Comparator.reverseOrder()); // 소수 역순 정렬
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        isPrime();
        String testCase = br.readLine();
        while(!testCase.equals("0")){ // 0이 아닌 입력이라면
            for(int i = 0; i < primeList.size(); i++){ // 큰 소수부터 확인
                if(testCase.contains(primeList.get(i).toString())){
                    System.out.println(primeList.get(i));
                    break;
                }
            }
            testCase = br.readLine();
        }
    }
}

---

문제 풀이 전략

 

초기에 255자리의 문자열에 대해 어떻게 처리해야 하나 고민하다가 100,000까지만 소수로 확인한다는 것을 보고 판단했다.

 

에라토스테네스의 체를 활용하여 먼저 모든 소수를 구해두고, 역순으로 정렬한 뒤 포함관계를 살펴보자!

https://to-travel-coding.tistory.com/83 에라토스테네스의 체를 모르면 참고하자.

 

물론 100000까지라고 하면 너무 많은 소수가 저장될 것 같지만 9592개가 저장된다는 것을 보고 가능하다고 판단하여 진행했다.