Liệt kê các số nguyên tố theo thứ tự từ nhỏ đến lớn trong dãy số

28
Lập trình C++

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;
}