문제
A prime number is greater than 1 and divisible only by 1 and itself. Checking divisors up to the square root of n is enough.
Implement is_prime(n).
Input
n: The number to test.
Output
Return true if n is prime, otherwise 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 has no divisors other than 1 and 29.
예시 2
입력:
n = 21
예상 출력:
expected = False입력:
long long n = 21;
예상 출력:
bool expected = false;입력:
long n = 21;
예상 출력:
bool expected = false;설명
21 = 3 × 7, so it is not prime.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
Handle numbers below 2 first; they cannot be prime.
힌트 2
Test possible divisors only up to the square root of the number.
힌트 3
Watch out for even numbers and repeated factors, since one divisor is enough to disqualify primality.
예상 복잡도
O(sqrt(n)) time, O(1) extra space
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.