소수 판별

문제

소수는 1보다 크고 1과 자기 자신만으로 나누어떨어지는 수입니다. n의 제곱근까지의 약수만 확인하면 충분합니다.

is_prime(n)을 구현하세요.

n: 판별할 숫자입니다.

n이 소수이면 true, 아니면 false를 반환하세요.

-1,000 ≤ n ≤ 1,000,000,000,000

예시 1

입력:
n = 29

예상 출력:
expected = True

입력:
long long n = 29;

예상 출력:
bool expected = true;

입력:
long n = 29;

예상 출력:
bool expected = true;

29는 1과 29 외에 약수가 없습니다.

예시 2

입력:
n = 21

예상 출력:
expected = False

입력:
long long n = 21;

예상 출력:
bool expected = false;

입력:
long n = 21;

예상 출력:
bool expected = false;

21 = 3 × 7이므로 소수가 아닙니다.

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

2보다 작은 수는 먼저 처리하세요. 소수가 아닙니다.

힌트 2

약수 후보는 숫자의 제곱근까지만 검사하세요.

힌트 3

짝수와 반복되는 인수에 주의하세요. 약수 하나만 있어도 소수가 아닙니다.

예상 복잡도

시간 O(sqrt(n)), 추가 공간 O(1)

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.