Số nguyên tố, sàng Eratosthenes
Lý thuyết ngắn
Kiểm tra một số: thử chia cho d từ 2 đến √n. Cần biết nhiều số nhỏ hơn N: dùng sàng Eratosthenes – đánh dấu bội của từng số nguyên tố, độ phức tạp O(N log log N).
Kiểm tra một số: thử chia cho d từ 2 đến √n. Cần biết nhiều số nhỏ hơn N: dùng sàng Eratosthenes – đánh dấu bội của từng số nguyên tố, độ phức tạp O(N log log N).