Đề bài
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.
Ràng buộc
-1,000 ≤ n ≤ 1,000,000,000,000
Ví dụ
Ví dụ 1
Đầu vào:
n = 29
Kết quả mong đợi:
expected = TrueĐầu vào:
long long n = 29;
Kết quả mong đợi:
bool expected = true;Đầu vào:
long n = 29;
Kết quả mong đợi:
bool expected = true;Giải thích
29 has no divisors other than 1 and 29.
Ví dụ 2
Đầu vào:
n = 21
Kết quả mong đợi:
expected = FalseĐầu vào:
long long n = 21;
Kết quả mong đợi:
bool expected = false;Đầu vào:
long n = 21;
Kết quả mong đợi:
bool expected = false;Giải thích
21 = 3 × 7, so it is not prime.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Handle numbers below 2 first; they cannot be prime.
Gợi ý 2
Test possible divisors only up to the square root of the number.
Gợi ý 3
Watch out for even numbers and repeated factors, since one divisor is enough to disqualify primality.
Độ phức tạp mong đợi
O(sqrt(n)) time, O(1) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.