# 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$($\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)](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))$)
```
#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
}
}
```
giavinh650
Created at
0 likes