Tích các nút nguyên tố trong danh sách liên kết đơn trong C++

Cho n nút trong danh sách liên kết đơn, nhiệm vụ là in ra tích của tất cả các nút nguyên tố (nút có giá trị là số nguyên tố).

Đầu vào

10 20 30 40 50

Đầu ra

4,00,000

Giải thích − Nút 10 ở vị trí 1 (không nguyên tố) bỏ qua. Nút 20 ở vị trí 2 (nguyên tố) tính. Tương tự 40, 50 ở vị trí nguyên tố.

Tích = 20 * 40 * 50 = 4,00,000

Nút màu đỏ là các nút nguyên tố

Phương pháp tiếp cận

• Tạo con trỏ tạm trỏ đến nút đầu (head)
• Duyệt qua từng nút, kiểm tra vị trí (index) có phải số nguyên tố không
• Nếu là vị trí nguyên tố: tích *= giá trị nút
• Chuyển sang nút tiếp theo
• In kết quả

Thuật toán

Bước 1 → Cấu trúc nút:
struct Node {
    int data;
    Node* next;
}

Bước 2 → Hàm thêm nút:
void themDau(Node** head_ref, int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = *head_ref;
    *head_ref = newNode;
}

Bước 3 → Kiểm tra số nguyên tố:
bool laNguyenTo(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6)
        if (n % i == 0 || n % (i+2) == 0) return false;
    return true;
}

Bước 4 → Tính tích:
void tinhTich(Node* head) {
    long long tich = 1;
    Node* ptr = head;
    int index = 1;
    while (ptr != NULL) {
        if (laNguyenTo(index))
            tich *= ptr->data;
        ptr = ptr->next;
        index++;
    }
    cout << "Tích các nút nguyên tố = " << tich;
}

Ví dụ mã nguồn

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

void themDau(Node** head_ref, int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = *head_ref;
    *head_ref = newNode;
}

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

void tinhTich(Node* head) {
    long long tich = 1;
    Node* ptr = head;
    int index = 1;
    while (ptr != NULL) {
        if (laNguyenTo(index))
            tich *= ptr->data;
        ptr = ptr->next;
        index++;
    }
    cout << "Tích các nút nguyên tố = " << tich;
}

int main() {
    Node* head = NULL;
    themDau(&head, 10);
    themDau(&head, 2);
    themDau(&head, 7);
    themDau(&head, 6);
    themDau(&head, 85);
    tinhTich(head);
    return 0;
}

Kết quả chạy chương trình

Tích các nút nguyên tố = 14