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

#1


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 :smiley:

#2

100k slot sao ko đủ bạn :slight_smile: 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

4 Likes
#3

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

#4

Sàng phân đoạn :slight_smile:

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.

4 Likes
#5

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.

5 Likes
#6

Mình thấy có bài viết này hướng dẫn sàng phân đoạn chi tiết này, bạn xem thử


Ngoài ra mình còn có ý tưởng chặt nhị phân dựa vào : hàm pi(x) và prime-gap bé nhưng chưa code xong =))

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?