백준 - 1816 암호 키 [완전탐색]

1816번: 암호 키

 

무식하지만 힘쎈 아이

 

백준 - 1816번 문제입니다.

 

해당 문제는 숫자가 주어지고 해당 숫자가 1,000,000 보다 큰 소인수로 이루어져 있다면 "YES"를 출력하고 아니면 "NO"를 출력하는 문제입니다.

 

다양한 방법으로 최적화가 가능하지만, 해당 문제의도에 맞게 가능한 모든 경우의 수를 넣는 방식인 완전탐색으로 풀어보겠습니다.

시간과 메모리가 충분하다면, 그 어떤 문제도 해결할 수 있는 아주 강력한 방법입니다.

# Python
for _ in range(int(input())):
    num = int(input())

    for i in range(2, 1_000_001):
        if num % i == 0:
            isTrue = False
            print("NO")
            break
        
    if i == 1_000_000:
        print("YES")

// Java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        for (int i = 0; i < n; i++) {
            long num = sc.nextLong();
            boolean isTrue = true;

            for (int j = 2; j <= 1_000_000; j++) {
                if (num % j == 0) {
                    System.out.println("NO");
                    isTrue = false;
                    break;
                }
            }
            if (isTrue) {
                System.out.println("YES");
            }
        }
    }
}

 

 

깃허브 소스코드