Dễ 7 đã giải Tỷ lệ chấp nhận 38.9%

Prime Number Check

Decide whether a number is prime.

Bạn sẽ học được gì

  • Test divisibility with the % operator
  • Stop checking at the square root of n
  • Handle 0, 1 and 2 as special cases

Đề bài

Xem bản dịch

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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 1,059 ms - 5/5 Xem code
2 AAmir Python 1,098 ms - - Xem code
3 KKKaneki Ken Python 1,137 ms - 5/5 Xem code
4 JPJittipat Phonhan Go 1,547 ms - 5/5 Xem code
5 GTGarlic The Destroyer Rust 1,759 ms - 2/5 Xem code
6 HJhettory Jurash C++ 4,287 ms - 4/5 Xem code
7 PTphúc thịnh phạm C++ 4,447 ms - 4/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 7 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.