# 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ố
Ta sẽ tạo sàng nguyên tố tương tự [bài này](https://marisaoj.com/problem/102), sau đó với mỗi giá trị nhập vào, ta đếm số lượng số nguyên tố mà giá trị đó chia hết, sau đó in ra màn hình.
> Ta có thể tối ưu cách duyệt để đếm ước bằng cách duyệt đến $\sqrt{n}$
Độ phức tạp tối ưu: $O$($\sqrt{n} * q$)
### Cách 2: Sàng ước nguyên tố
Ta sẽ cải tiến sàng nguyên tố để nó đánh dấu các ước nguyên tố của các số từ 1 đến $n$.
```
void sieve(int n)
{
int i,j;
for(i=2;i<=n;i++)
{
if (f[i]==0)
{
for(j=i;j<=n;j+=i) f[j]=i;
}
}
}
```
Sau đó, với mỗi giá trị nhập vào, ta lưu các ước nguyên tố của giá trị đó bằng cách lưu ước nguyên tố của giá trị $n$, đồng thời chia $n$ cho cùng ước nguyên tố đó đến khi nào không chia hết nữa thì lấy giá trị khác. Lặp lại đến khi $n$ bằng 1.
Độ phức tạp: $O$($q * \log(n)$)
## Bài giải:
> Giải thuật: sàng ước nguyên tố (sử dụng $set$ để lưu các giá trị ước nguyên tố)
> Độ phức tạp: $O$($q$ * $\log(n)^2$) (do mỗi lần xử lý với $set$ sẽ tốn $O(\log(n))$
```
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=1e6+10; int f[N]={};
void sieve(int n)
{
int i,j;
for(i=2;i<=n;i++)
{
if (f[i]==0)
{
for(j=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 n,x;
cin>>n; while (n--)
{
set<int> st;
set<int>::iterator it;
cin>>x;
while (x>1)
{
st.insert(f[x]); x/=f[x];
}
for(it=st.begin();it!=st.end();it++) cout<<*it<<" ";
cout<<endl;
}
}
```
giavinh650
Created at
5 likes