Liệt kê các số nguyên tố nhỏ hơn n

141
Lập trình C++

Bài toán: Cho số nguyên dương n (n <=107). Liệt kê các số nguyên tố nhỏ hơn hoặc bằng n (mỗi số cách nhau một dấu cách).

Với bài toán này, ta sử dụng một hàm xác định kiểm tra 1 số có phải là số nguyên tố hay không. Tiếp đó, duyệt lần lượt các số từ 1 đến n để liệt kê ra các số nguyên tố.

Code tham khảo:

#include <iostream>
#include <cmath>
using namespace std;
int nguyenTo(int n) {
    if (n < 2) return 0;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}
int main() {
    freopen("NGUYENTO.INP","r",stdin);
    freopen("NGUYENTO.OUT","w",stdout);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        if(nguyenTo(i) == 1) {
            cout << i << " ";
        }
    }
    return 0;
}

Tham khảo bài toán: kiểm tra một số nguyên n có phải là số nguyên tố hay không?

#include <iostream>
#include <cmath>
using namespace std;
int nguyenTo(int n) {
    if (n < 2) return 0;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}
int main() {
    freopen("NGUYENTO.INP","r",stdin);
    freopen("NGUYENTO.OUT","w",stdout);
    int n;
    cin >> n;
    if (nguyenTo(n)) cout << 1;
    else cout << -1;
    return 0;
}