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: Duyệt

Với mỗi số từ 1 đến $n$, ta kiểm tra số đó có phải là số nguyên tố hay không. Nếu số đó là số nguyên tố thì ta in ra màn hình. > Chúng ta có thể kiểm tra số nguyên tố tương tự bài số nguyên tố 2 để tăng tốc độ kiểm tra.

Độ phức tạp tối ưu là $O$($\sum_{k=1}^n \sqrt{k}$)

Cách 2: Sàng nguyên tố

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ố (VNOI)

Sieve of Eratosthenes (Wikipedia)

> Sau khi chúng ta hoàn thiện sàng nguyên tố thì chúng ta chỉ cần duyệt từ 2 đến $n$, rồi in ra những số chưa được đánh dấu.

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

Bài giải:

> Giải thuật: sàng nguyên tố

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

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