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

Kiểm Tra Số Nguyên Tố

Xác định xem một số có phải là số nguyên tố hay không.

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

  • Kiểm tra chia hết bằng toán tử %
  • Dừng kiểm tra tại căn bậc hai của n
  • Xử lý 0, 1 và 2 như trường hợp đặc biệt

Đề bài

Xem bản gốc (English)

Một số nguyên tố là số lớn hơn 1 và chỉ chia hết cho 1 và chính nó. Chỉ cần kiểm tra các ước số đến căn bậc hai của n là đủ.

Cài đặt hàm is_prime(n).

Đầu vào

n: Số cần kiểm tra.

Đầu ra

Trả về true nếu n là số nguyên tố, ngược lại trả về 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 không có ước số nào ngoài 1 và 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, nên không phải là số nguyên tố.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Xử lý các số nhỏ hơn 2 trước; chúng không thể là số nguyên tố.

Gợi ý 2

Chỉ thử các ước tiềm năng đến căn bậc hai của số đó.

Gợi ý 3

Lưu ý số chẵn và các thừa số lặp lại, vì chỉ cần một ước là đủ để loại tính nguyên tố.

Độ phức tạp mong đợi

thời gian O(sqrt(n)), bộ nhớ phụ O(1)

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.