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

rogp10 viết 16:35 ngày 01/10/2018

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

Trần Việt Huy viết 16:39 ngày 01/10/2018

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???

rogp10 viết 16:38 ngày 01/10/2018

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ới sieve[i] đại diện cho i+l. Để tìm khởi điểm ta tính l mod p.

Gió viết 16:41 ngày 01/10/2018

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.

Bài liên quan
0