# 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](https://marisaoj.com/problem/25) để tăng tốc độ kiểm tra.
Độ phức tạp tối ưu là O(∑nk=1√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)](https://wiki.vnoi.info/algo/algebra/prime_sieve.md)
[Sieve of Eratosthenes (Wikipedia)](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
> 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)))
#∈clude<bitsstdc++.h>#def∈e∫longlong#def∈eendl\nusingnamespacestd;const∫N=2e6+10;∫f[N]={};voieve(∫n)/hà