19/11/2018, 19:41

Liệt kê tất cả các số nguyên tố nhỏ hơn n trong C++

Học lập trình C++ Đề bài : viết chương trình liệt kê tất cả các số nguyên tố nhỏ hơn n. Định nghĩa Số nguyên tố là số lớn hơn 1 và chỉ chia hết cho 1 và chính nó. Ví dụ: 2, 3, 5, 7, 11, 13, 17, … là những số nguyên tố. Chú ý : Số 0 và 1 không phải là số nguyên ...

Học lập trình C++

Đề bài: viết chương trình liệt kê tất cả các số nguyên tố nhỏ hơn n.

Định nghĩa

Số nguyên tố là số lớn hơn 1 và chỉ chia hết cho 1 và chính nó.
Ví dụ: 2, 3, 5, 7, 11, 13, 17, … là những số nguyên tố.
Chú ý: Số 0 và 1 không phải là số nguyên tố. Chỉ có số 2 là số nguyên tố chẵn, tất cả các số chẵn khác không phải là số nguyên tố vì chúng chia hết cho 2.

Lời giải

/**
 * Chuong liet ke cac so nguyen to nho hon n.
 * 
 * @author viettuts.vn
 */
 
#include <iostream>
#include <cmath>
 
using namespace std;

/**
 * check so nguyen to
 * 
 * @author viettuts.vn
 * @param n: so nguyen duong
 * @return 1: la so nguyen so, 
 *         0: khong la so nguyen to
 */
int isPrimeNumber(int n) {
    // so nguyen n < 2 khong phai la so nguyen to
    if (n < 2) {
        return 0;
    }
    // check so nguyen to khi n >= 2
    int i;
    int squareRoot = (int) sqrt(n);
    for (i = 2; i <= squareRoot; i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

/**
 * Ham main
 */
int main() {
	int i, n;
    cout << "Nhap n = ";
    cin >> n;
    printf("Tat ca cac so nguyen to nho hon %d la: 
", n);
    if (n >= 2) {
        printf("%d ", 2);
    }
    for (i = 3; i < n; i+=2) {
        if (isPrimeNumber(i) == 1) {
            printf("%d ", i);
        }
    }
}

Kết quả:

Nhập n = 100
Tat ca cac so nguyen to nho hon 100 la: 
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Học lập trình C++
0