백준 1313번 합성소수

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

 

T번 동안 들어오는 N에 대해서 N보다 작은  세자릿수 이상의 합성소수들 중 가장 큰 수를 출력하는 문제이다. 합성소수를 일일이 구하려고 했으나 시간 초과가 발생하여 다른 방법을 찾아 본 결과, 에라토스테네스의 체를 적용하여 100부터 N까지 미리 합성수인지  소수인지 판별하고, N이 합성소수인지 확인만 하면 된다.

 

먼저 2부터 N의 최대값인 10^7까지 배수를 적용하여 합성수인지 판별한다.

for (int i = 2; (long) i * i <= MAX; i++) {
    if (!isComposite[i]) {
        for (int j = i * i; j <= MAX; j += i) {
            isComposite[j] = true;
        }
    }
}

 

 

이후, 100부터 10^7까지 합성소수인지 판별한다. 판별 후, 합성소수면 해당 수를, 아니면 이전의 가장 큰 합성소수를 누적한다.

static boolean isCompositePrime(int n) {
    if (n < 100) {
        return false;
    }
    
    if (!isComposite[n]) {
        return false;
    }
    
    char[] s = Integer.toString(n).toCharArray();
    int len = s.length;
    
    for (int i = 0; i < len; i++) {
        for (int j = i + 2; j <= len; j++) {
            if (i == 0 && j == len) {
                continue;
            }
            
            int sub = 0;
            for (int k = i; k < j; k++) {
                sub = sub * 10 + (s[k] - '0');
            }
            
            if (sub < 2 || isComposite[sub]) {
                return false;
            }
        }
    }
    
    return true;
}

 

for (int n = 100; n <= MAX; n++) {
    maxCP[n] = maxCP[n - 1];
    if (isCompositePrime(n)) {
        maxCP[n] = n;
    }
}

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class 합성소수1313 {
    
    static final int MAX = 10_000_000;
    static boolean[] isComposite = new boolean[MAX + 1];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        isComposite[0] = isComposite[1] = true;
        for (int i = 2; (long) i * i <= MAX; i++) {
            if (!isComposite[i]) {
                for (int j = i * i; j <= MAX; j += i) {
                    isComposite[j] = true;
                }
            }
        }
        
        int[] maxCP = new int[MAX + 1];
        Arrays.fill(maxCP, -1);
        
        for (int n = 100; n <= MAX; n++) {
            maxCP[n] = maxCP[n - 1];
            if (isCompositePrime(n)) {
                maxCP[n] = n;
            }
        }
        
        int T = Integer.parseInt(br.readLine().trim());
        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine().trim());
            sb.append(maxCP[n]).append('\n');
        }
        
        System.out.print(sb);
    }
    
    static boolean isCompositePrime(int n) {
        if (n < 100) {
            return false;
        }
        
        if (!isComposite[n]) {
            return false;
        }
        
        char[] s = Integer.toString(n).toCharArray();
        int len = s.length;
        
        for (int i = 0; i < len; i++) {
            for (int j = i + 2; j <= len; j++) {
                if (i == 0 && j == len) {
                    continue;
                }
                
                int sub = 0;
                for (int k = i; k < j; k++) {
                    sub = sub * 10 + (s[k] - '0');
                }
                
                if (sub < 2 || isComposite[sub]) {
                    return false;
                }
            }
        }
        
        return true;
    }
}