Bài tập C – Liệt kê n số nguyên tố đầu tiên – VietTuts

Posted on by mtoplistChuyên mục:Top List

Nội dung chính

  • Đề bài
  • Lời giải

Đề bài

Viết chương trình C liệt kê n số nguyên tố đầu tiê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 trinh liet ke n so nguyen to dau tien.
 * 
 * @author viettuts.vn
 */
 #include<stdio.h>
 #include<math.h>

/**
 * 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 = sqrt(n);
    for (i = 2; i <= squareRoot; i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

/**
 * Ham main
 */
int main() {
 int n;
    printf("Nhap n = ");
    scanf("%d", &n);
    printf("%d so nguyen to dau tien la: \n", n);
    int dem = 0; // dem tong so nguyen to
    int i = 2;   // tim so nguyen to bat dau tu so 2
    while (dem < n) {
        if (isPrimeNumber(i)) {
            printf("%d ", i);
            dem++;
        }
        i++;
    }
}

Kết quả: 

Nhập n = 10
10 so nguyen to dau tien la: 
2 3 5 7 11 13 17 19 23 29

mtoplist