Ước nguyên tố2
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Người đăng:
Dạng bài
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Bình luận
include<bits/stdc++.h> using namespace std; bool ngto[1000007]; void sang() { memset(ngto,true,sizeof ngto); ngto[0]=false; ngto[1]=false; for(int i=2;ii<=1e6;i++) { if(ngto[i]==true) for(int j=ii;j<=1000007;j+=i) ngto[j]=false; }
} long long a,b,f[1000007]; int main() {
sang(); for(int i=2;i<=1000007;i++) { if(ngto[i]==true) { for(int j=i;j<=1000007;j+=i) f[j]=i; } } iosbase::syncwith_stdio(false); cin.tie(NULL);cout.tie(NULL); cin>>a; while(a--) { cin>>b; cout<<f[b]<<'\n'; } }