Nhắc nhở:

Khuyến khích mọi người nên tự tìm hiểu, suy nghĩ lời giải trước khi tham khảo

Nên đọc kỹ hướng dẫn trước khi tham khảo bài làm

Cách 1: Sàng nguyên tố trên đoạn

Các bạn có thể tham khảo hướng dẫn tại các trang này

Sàng nguyên tố khái quát

Sàng nguyên tố trên đoạn (video)

Giải thích thuật toán:

Áp dụng cách làm của sàng nguyên tố từ bài này, ta sẽ duyệt từ 2 đến $\sqrt{R}$. Nhưng thay vì đánh dấu trực tiếp trên đoạn từ $L$ đến $R$, ta sẽ đánh dấu lại vào 1 mảng con với độ dài tương tự (nhưng giá trị $L$ sẽ có vị trí trong mảng con từ 0, và các giá trị sau đó cũng sẽ bớt đi $L$ giá trị). Sau đó, với mỗi giá trị từ 2 đến $\sqrt{R}$, ta sẽ đánh dấu lại các giá trị tương ứng chia hết cho nó (tất nhiên ta sẽ bớt đi $L$ giá trị của số đó để đánh dấu được vào mảng con). Sau khi đánh dấu, việc còn lại là duyệt trên mảng con, nếu số nào chưa được đánh dấu là hợp số thì in ra màn hình.

> Với ($R-L+1$) $\le$ $10^6$, và $R$ $\le$ $10^{12}$ (tức $\sqrt{R}$ $\le$ $10^{6}$), ta có thể sàng trên đoạn từ $L$ đến $R$ mà không bị quá thời gian.

Độ phức tạp: $O$($N$ * $\log(n)$)

Bài giải:

> Giải thuật: sàng nguyên tố trên đoạn

> Độ phức tạp: $O$($N$ * $\log(n)$)

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=1e6+10; int f[N]={}; //f[] là mảng con để đánh dấu
void sieve(int l, int r) //sàng nguyên tố trên đoạn
{
    int i,j,sqrtn=sqrt(r);
    for(i=2;i<=sqrtn;i++)
    {
        for(j=max(i*i,(l+i-1)/i*i);j<=r;j+=i) f[j-l]++;
    }
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int i,l,r;
    cin>>l>>r;
    sieve(l,r);
    for(i=max(2ll,l);i<=r;i++)
    {
        if (f[i-l]==0) cout<<i<<" "; //in ra màn hình các số chưa được đánh dấu là hợp số
    }
}