01/10/2018, 14:27
Hỏi về cách đếm số lượng số nguyên tố trong đoạn [l,r] mà 1 <= l <= r < 2^31, l – r <= 100000
spoj.com
SPOJ.com - Problem ALGOPRO9
...
mọi người giúp em bài này với ạ, em đã thử làm cả bình thường cả sàng số nguyên tố nhưng vẫn khong được, hình như sàng thì n mangr khong nhớ đủ, mọi người giúp em với, em xin cảm ơn
Bài liên quan
100k slot sao ko đủ bạn chỉ dùng 100k slot.
Dành cho bạn đọc: Tích ước = BCNN thì nó ntn, do ước là số chia hết số khác nên BCNN của các ước chính là số ban đầu vậy (tính luôn chính nó mà). Tích ước tối thiểu cũng phải là số ban đầu, vậy nó là nguyên tố :v
khoảng là 100000 với mỗi test. Nếu mình sàng thì phải sàng 2^31~10^9 roi, làm sao sàng được???
Sàng phân đoạn
Trước hết ta chạy sàng từ 2 đến
sqrt(r)như bt để lấy ds số nguyên tố.Rồi đặt
sieve[0..r-l]vớisieve[i]đại diện choi+l. Để tìm khởi điểm ta tínhl mod p.Ngoài cách dùng sàng phân đoạn, bạn có thể dùng hàm đếm số nguyên tố để làm việc với bài toán đếm số nguyên tố trong khoảng lớn hơn.