Tìm Số Nguyên Tố Từ 2 Đến 100 Trong C: Hướng Dẫn Chi Tiết và Tối Ưu SEO

Bạn đang tìm cách viết một chương trình C để tìm tất cả các **số nguyên tố** trong một phạm vi nhất định? Bài viết này sẽ hướng dẫn bạn từng bước cách thực hiện điều đó, đồng thời cung cấp các giải thích chi tiết để bạn hiểu rõ hơn về thuật toán và cách tối ưu hóa code. Việc tìm **số nguyên tố trong C** không chỉ là một bài tập lập trình cơ bản mà còn là cơ hội để bạn nắm vững các khái niệm quan trọng trong lập trình và thuật toán.

Số Nguyên Tố Là Gì?

Trước khi bắt đầu viết code, hãy cùng nhau ôn lại khái niệm **số nguyên tố**. Một số nguyên tố là một số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó. Ví dụ: 2, 3, 5, 7, 11, 13,... là các số nguyên tố.

Cách Tiếp Cận Bài Toán Tìm Số Nguyên Tố

Để tìm **số nguyên tố** trong một phạm vi cho trước (ví dụ: từ 2 đến 100), chúng ta có thể sử dụng một thuật toán đơn giản: duyệt qua từng số trong phạm vi đó và kiểm tra xem số đó có phải là số nguyên tố hay không. Để kiểm tra một số có phải là số nguyên tố hay không, ta chỉ cần kiểm tra xem số đó có chia hết cho bất kỳ số nào từ 2 đến căn bậc hai của nó hay không. Nếu không chia hết cho số nào trong phạm vi đó, thì số đó là số nguyên tố.

Code C Cơ Bản Để Tìm Số Nguyên Tố

Dưới đây là một đoạn code C cơ bản để tìm các **số nguyên tố từ 2 đến 100**:

    
#include <stdio.h>

int prime(int n) {
  int j;
  for (j = 2; j <= n / 2; j++) {
    if ((n % j) == 0) {
      return 0;
    } else {
      return 1;
    }
  }
  return 1; // Thêm dòng này để xử lý trường hợp n <= 1
}

int main() {
  int i, p;
  for (i = 2; i <= 100; i++) {
    p = prime(i);
    if (p == 1) {
      printf("%d \n", i);
    }
  }
  return 0;
}
    
  

Tuy nhiên, đoạn code trên có một lỗi nhỏ. Hàm `prime()` sẽ luôn trả về sau lần lặp đầu tiên. Để sửa lỗi này, ta cần thay đổi cấu trúc của hàm như sau:

    
#include <stdio.h>

int prime(int n) {
  int j;
  for (j = 2; j <= n / 2; j++) {
    if ((n % j) == 0) {
      return 0; // Nếu chia hết, không phải số nguyên tố
    }
  }
  return 1; // Nếu không chia hết cho số nào, là số nguyên tố
}

int main() {
  int i;
  for (i = 2; i <= 100; i++) {
    if (prime(i)) {
      printf("%d \n", i);
    }
  }
  return 0;
}
    
  

Giải Thích Code

• #include <stdio.h>: Khai báo thư viện chuẩn để sử dụng các hàm nhập/xuất dữ liệu (ví dụ: `printf`).
• Hàm prime(int n):
  • Nhận một số nguyên `n` làm đầu vào.
  • Duyệt qua các số từ 2 đến `n / 2`.
  • Nếu `n` chia hết cho bất kỳ số nào trong phạm vi này, hàm trả về 0 (không phải số nguyên tố).
  • Nếu `n` không chia hết cho bất kỳ số nào, hàm trả về 1 (là số nguyên tố).
• Hàm main():
  • Duyệt qua các số từ 2 đến 100.
  • Gọi hàm prime() để kiểm tra xem mỗi số có phải là số nguyên tố hay không.
  • Nếu số đó là số nguyên tố, in ra màn hình.

Tối Ưu Hóa Code Tìm Số Nguyên Tố Trong C

Chúng ta có thể tối ưu hóa code trên bằng cách:

• Chỉ kiểm tra các số lẻ sau khi đã kiểm tra số 2. Vì tất cả các số chẵn lớn hơn 2 đều không phải là số nguyên tố.
• Chỉ duyệt đến căn bậc hai của `n` thay vì `n / 2`. Vì nếu `n` có một ước số lớn hơn căn bậc hai của nó, thì nó cũng phải có một ước số nhỏ hơn căn bậc hai của nó.

Đây là đoạn code đã được tối ưu hóa:

    
#include <stdio.h>
#include <math.h>

int isPrime(int n) {
    if (n <= 1) return 0;
    if (n <= 3) return 1;
    if (n % 2 == 0 || n % 3 == 0) return 0;
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;
    return 1;
}

int main() {
    int n = 100;
    for (int i = 2; i <= n; i++) {
        if (isPrime(i))
            printf("%d ", i);
    }
    return 0;
}

    
  

Kết Luận

Trong bài viết này, chúng ta đã tìm hiểu cách viết chương trình C để tìm **số nguyên tố từ 2 đến 100**. Chúng ta cũng đã thảo luận về cách tối ưu hóa code để tăng hiệu suất. Hy vọng bài viết này sẽ giúp bạn hiểu rõ hơn về **thuật toán tìm số nguyên tố trong C** và cách áp dụng nó vào các bài toán lập trình khác. Chúc bạn thành công trên con đường chinh phục lập trình!