Kiểm Tra Số Nguyên Tố

Đề bài

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).

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

Trả về true nếu n là số nguyên tố, ngược lại trả về false.

-1.000 ≤ n ≤ 1.000.000.000.000

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;

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;

21 = 3 × 7, nên không phải là số nguyên tố.

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)

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.