소수 판별

문제

2 이상의 정수 N이 주어집니다. N이 소수인지 합성수인지 판별하세요.

소수란 1과 자기 자신만으로 나누어 떨어지는 2 이상의 자연수를 말합니다. 예를 들어 2, 3, 5, 7, 11 등은 소수이고, 4, 6, 8, 9 등은 합성수입니다.

제한

• 2 ≤ N ≤ 1,000,000

예제

입력 1

17

출력 1

prime

17은 1과 17 외에는 나누어 떨어지는 수가 없으므로 소수입니다.

입력 2

4

출력 2

composite

4 = 2 × 2이므로 합성수입니다.

힌트: 어떤 수 N이 합성수라면, N의 약수 중 하나는 반드시 √N 이하입니다. 따라서 2부터 √N까지만 확인해도 소수를 판별할 수 있습니다.