Lời giải

Không thể sàng tới ~10^{12}~, nhưng độ dài đoạn chỉ tối đa ~10^6~ nên có thể sàng trên đoạn:

• Mọi hợp số ~m \le R~ đều có một ước nguyên tố không vượt quá ~\sqrt{R} \le 10^6~. Hãy sàng trước các số nguyên tố đến ~\sqrt{R}~.
• Với mỗi số nguyên tố ~p~ tìm được, đánh dấu các bội của ~p~ trong đoạn ~[L, R]~, bắt đầu từ bội nhỏ nhất không nhỏ hơn ~\max(p^2, L)~.
• Những vị trí còn lại chính là số nguyên tố.

Hãy chú ý hai điểm: ~p^2~ có thể vượt quá phạm vi 32 bit, và ~1~ không phải số nguyên tố nên phải loại riêng khi ~L = 1~.