SWEA 16002. 합성수 방정식

차이가 n인 두 합성수를 찾는 문제이다. 합성수는 1과 자신이 아닌 약수가 존재하는 수 이며, n<=10^7 이다.

 

자연수인 합성수는 4 이상이며, 차이가 n인 수를 찾아야 하므로 4+n부터 순차적으로 i, i-n이 모두 합성수이면 차이가 n인 합성수를 찾게 된다.

private static boolean isNotPrimeNumber(int n) {
    for(int i=2; i<=Math.sqrt(n); i++) {
        if(n % i == 0) return true;
    }
    return false;
}

for(int i = n+4; i <= 1_000_000_000; i++) {
    if(isNotPrimeNumber(i) && isNotPrimeNumber(i-n)) {
        sb.append(i).append(" ").append(i-n).append('\n');
        break;
    }
}

 

 

결과 코드는 다음과 같다.

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

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int tc = 1; tc <= T; tc++) {
            sb.append('#').append(tc).append(' ');
            int n = Integer.parseInt(br.readLine());
            for(int i = n+4; i <= 1_000_000_000; i++) {
                if(isNotPrimeNumber(i) && isNotPrimeNumber(i-n)) {
                    sb.append(i).append(" ").append(i-n).append('\n');
                    break;
                }
            }
        }
        
        br.close();
        System.out.print(sb);
    }
    
    private static boolean isNotPrimeNumber(int n) {
        for(int i=2; i<=Math.sqrt(n); i++) {
            if(n % i == 0) return true;
        }
        return false;
    }
}