Bài toán. Liệt kê các số nguyên tố theo thứ tự từ nhỏ đến lớn trong dãy số a. Ví dụ:
|
NTO.INP |
NTO.OUT |
|
10 3 4 7 2 9 31 16 29 37 9 |
2 3 7 29 31 37 |
Code tham khảo:
#include <iostream>
#include <algorithm>
#define nmax 1000007
using namespace std;
int n,a[nmax],f[nmax],c[nmax];
void sangNto(int u) {
for(int i = 1;i <= u;i++)
f[i] = 1;
f[1] = 0;
for(int i = 2;i <= u/2;i++)
if(f[i] == 1)
for(int j=i;j<=u/2;j++)
f[i*j] = 0;
}
int main() {
freopen("NTO.INP","r",stdin);
freopen("NTO.OUT","w",stdout);
int h = 0;
cin >> n;
int rmax = -999999999;
for(int i = 1;i <= n;i++) {
cin >> a[i];
rmax = max(rmax,a[i]);
}
sangNto(rmax);
for(int i = 1;i <= n;i++)
if(f[a[i]] == 1)
c[++h] = a[i];
sort(c + 1, c + h + 1);
for(int i = 1;i <= h;i++)
cout << c[i]<<" ";
if(h == 0) cout << -1;
return 0;
}