Tổng các số nguyên tố trong mảng 1 chiều C/C++ – Lập trình C – phanmemdohoa.com

Tìm tổng các số nguyên tố trong mảng một chiều là một bài toán phổ biến khi học lập trình C/C++. Bài viết này sẽ giúp bạn hiểu rõ về cách xác định số nguyên tố và các phương pháp tính tổng chúng trong mảng một cách hiệu quả. ✨

Số nguyên tố là gì?

Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có đúng hai ước số là 1 và chính nó. Ví dụ: 2, 3, 5, 7, 11, 13… là các số nguyên tố.

Số nguyên tố đóng vai trò quan trọng trong toán học và khoa học máy tính, đặc biệt trong mã hóa và bảo mật thông tin.

Để kiểm tra một số có phải là số nguyên tố hay không, chúng ta cần xác định xem nó 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.

Thuật toán kiểm tra số nguyên tố

Để xác định một số có phải là số nguyên tố hay không, chúng ta sẽ sử dụng thuật toán sau:
c#include <stdio.h>
#include <math.h>
#include <stdbool.h>

// Hàm kiểm tra số nguyên tố
bool isPrime(int num) {
// Số nhỏ hơn 2 không phải số nguyên tố
if (num < 2) return false;

// Kiểm tra từ 2 đến căn bậc hai của số
for (int i = 2; i <= sqrt(num); i++) {
    if (num % i == 0) return false;
}

return true;

}
Thuật toán trên có độ phức tạp O(√n), hiệu quả hơn nhiều so với việc kiểm tra tất cả các số từ 2 đến n-1.

Bài toán tổng các số nguyên tố trong mảng

Bài toán đặt ra như sau: Cho một mảng một chiều gồm n phần tử nguyên. Hãy tính tổng các phần tử là số nguyên tố trong mảng đó.

Các bước giải quyết bài toán:

1. Khởi tạo mảng và nhập dữ liệu
2. Duyệt qua từng phần tử trong mảng
3. Kiểm tra mỗi phần tử có phải số nguyên tố hay không
4. Nếu là số nguyên tố thì cộng vào tổng
5. Hiển thị kết quả

Chương trình hoàn chỉnh tính tổng số nguyên tố trong mảng

Dưới đây là chương trình C/C++ hoàn chỉnh để tính tổng các số nguyên tố trong mảng một chiều:
c#include <stdio.h>
#include <math.h>
#include <stdbool.h>

// Hàm kiểm tra số nguyên tố
bool isPrime(int num) {
if (num < 2) return false;

for (int i = 2; i <= sqrt(num); i++) {
    if (num % i == 0) return false;
}

return true;

}

// Hàm nhập mảng
void inputArray(int arr[], int n) {
printf(“Nhập các phần tử của mảng:n”);
for (int i = 0; i < n; i++) {
printf(“Phần tử thứ %d: “, i + 1);
scanf(“%d”, &arr[i]);
}
}

// Hàm hiển thị mảng
void displayArray(int arr[], int n) {
printf(“Các phần tử trong mảng: “);
for (int i = 0; i < n; i++) {
printf(“%d “, arr[i]);
}
printf(“n”);
}

// Hàm tính tổng số nguyên tố
int sumPrimeNumbers(int arr[], int n) {
int sum = 0;
int primeCount = 0;

printf("Các số nguyên tố trong mảng: ");
for (int i = 0; i < n; i++) {
    if (isPrime(arr[i])) {
        printf("%d ", arr[i]);
        sum += arr[i];
        primeCount++;
    }
}

printf("nSố lượng số nguyên tố: %dn", primeCount);
return sum;

}

int main() {
int arr[100]; // Mảng tối đa 100 phần tử
int n;

printf("Nhập số lượng phần tử của mảng: ");
scanf("%d", &n);

inputArray(arr, n);
displayArray(arr, n);

int sum = sumPrimeNumbers(arr, n);
printf("Tổng các số nguyên tố: %dn", sum);

return 0;

}

Giải thích chi tiết mã nguồn

1. Hàm isPrime

Hàm isPrime kiểm tra xem một số có phải là số nguyên tố hay không:

• Nếu số nhỏ hơn 2, trả về false (không phải số nguyên tố)
• Kiểm tra xem số có chia hết cho số nào từ 2 đến căn bậc hai của nó hay không
• Nếu không có số nào chia hết, trả về true (là số nguyên tố)

2. Hàm inputArray và displayArray

Hai hàm này giúp nhập và hiển thị mảng một cách có tổ chức, giúp code dễ đọc và bảo trì hơn.

3. Hàm sumPrimeNumbers

Đây là hàm chính thực hiện việc tính tổng các số nguyên tố:

• Duyệt qua từng phần tử trong mảng
• Kiểm tra mỗi phần tử có phải số nguyên tố bằng hàm isPrime
• Nếu là số nguyên tố, hiển thị nó và cộng vào tổng
• Đồng thời đếm số lượng số nguyên tố để thống kê

4. Hàm main

Hàm main điều phối luồng chương trình:

• Khai báo mảng với kích thước tối đa
• Nhập số lượng phần tử
• Gọi các hàm để nhập mảng, hiển thị và tính tổng số nguyên tố

Ví dụ minh họa thuật toán

Giả sử chúng ta có mảng: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Quá trình xác định số nguyên tố và tính tổng:

Các số nguyên tố trong mảng là: 2, 3, 5, 7

Tổng các số nguyên tố: 2 + 3 + 5 + 7 = 17

Tối ưu hóa chương trình

Để tối ưu hóa chương trình, chúng ta có thể áp dụng một số kỹ thuật sau:

1. Cải tiến thuật toán kiểm tra số nguyên tố

Đối với số chẵn lớn hơn 2, chúng ta có thể loại trừ ngay vì chúng không phải số nguyên tố:
cbool isPrime(int num) {
if (num < 2) return false;
if (num == 2) return true;
if (num % 2 == 0) return false; // Loại bỏ số chẵn lớn hơn 2

// Chỉ kiểm tra các số lẻ
for (int i = 3; i <= sqrt(num); i += 2) {
    if (num % i == 0) return false;
}

return true;

}

2. Sử dụng Sàng Eratosthenes cho nhiều số

Nếu mảng có nhiều phần tử và giá trị lớn, có thể sử dụng Sàng Eratosthenes để xác định nhanh các số nguyên tố:
cvoid sieveOfEratosthenes(bool isPrime[], int max) {
// Khởi tạo tất cả là số nguyên tố
for (int i = 0; i <= max; i++) {
isPrime[i] = true;
}

isPrime[0] = isPrime[1] = false; // 0 và 1 không phải số nguyên tố

for (int i = 2; i * i <= max; i++) {
    if (isPrime[i]) {
        // Đánh dấu tất cả bội của i là không phải số nguyên tố
        for (int j = i * i; j <= max; j += i) {
            isPrime[j] = false;
        }
    }
}

}

Bài tập thực hành

Để hiểu sâu hơn về bài toán này, bạn có thể thử một số bài tập sau:

1. Mở rộng chương trình để tìm tích các số nguyên tố trong mảng
2. Sửa đổi chương trình để tìm số nguyên tố lớn nhất và nhỏ nhất trong mảng
3. Viết chương trình đếm số lượng các số nguyên tố nằm ở vị trí chẵn trong mảng
4. Tạo một hàm sắp xếp các số nguyên tố trong mảng theo thứ tự tăng dần

Các lỗi thường gặp và cách khắc phục ⚠️

Kết luận

Bài toán tìm tổng các số nguyên tố trong mảng một chiều là một bài toán cơ bản nhưng quan trọng trong lập trình C/C++. Thông qua bài toán này, chúng ta đã học được:

• Cách xác định số nguyên tố hiệu quả
• Phương pháp xử lý mảng một chiều
• Kỹ thuật tối ưu hóa thuật toán
• Tổ chức mã nguồn theo cấu trúc rõ ràng

Hy vọng bài viết này đã giúp bạn hiểu rõ về cách giải quyết bài toán và có thể áp dụng vào các bài tập lập trình khác. Nếu có thắc mắc, hãy để lại bình luận bên dưới!

Chúc bạn học tập hiệu quả!

Tài liệu tham khảo:

• Wikipedia – Số nguyên tố
• Moz – SEO Algorithm
• Photoshop
• Autocad