โปรแกรมหาผลคูณโหนดที่เป็นจำนวนเฉพาะใน Singly Linked List ด้วย C++

ภาพรวมปัญหา

โปรแกรมนี้คำนวณผลคูณของข้อมูลในโหนด (nodes) ของ Singly Linked List ที่มี ค่าข้อมูลเป็นจำนวนเฉพาะ (Prime Number) ไม่ใช่ตำแหน่ง (index) ที่เป็นจำนวนเฉพาะ

หมายเหตุสำคัญ: โค้ดต้นฉบับมีความสับสนระหว่าง "Prime Index" (ตำแหน่งที่เป็นจำนวนเฉพาะ) และ "Prime Data" (ค่าข้อมูลที่เป็นจำนวนเฉพาะ) โค้ดตัวอย่างจริงๆ ตรวจสอบค่าข้อมูล (data) ว่าเป็นจำนวนเฉพาะ ไม่ใช่ index

โครงสร้างข้อมูล Linked List

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

ฟังก์ชันตรวจสอบจำนวนเฉพาะ

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;      // 2, 3 เป็นจำนวนเฉพาะ
    if (n % 2 == 0 || n % 3 == 0) return false;
    
    // ตรวจสอบตัวหารรูปแบบ 6k ± 1
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

ฟังก์ชันคำนวณผลคูณโหนดเฉพาะ

long long productOfPrimeNodes(Node* head) {
    long long product = 1;
    Node* current = head;
    bool foundPrime = false;
    
    while (current != nullptr) {
        if (isPrime(current->data)) {
            product *= current->data;
            foundPrime = true;
        }
        current = current->next;
    }
    
    return foundPrime ? product : 0;  // คืน 0 ถ้าไม่มีโหนดเฉพาะ
}

โปรแกรมสมบูรณ์พร้อมทดสอบ

#include <iostream>
using namespace std;

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

// เพิ่มโหนดที่หัวรายการ
void push(Node** headRef, int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = *headRef;
    *headRef = newNode;
}

bool isPrime(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;
}

long long productOfPrimeNodes(Node* head) {
    long long product = 1;
    bool found = false;
    while (head) {
        if (isPrime(head->data)) {
            product *= head->data;
            found = true;
        }
        head = head->next;
    }
    return found ? product : 0;
}

void printList(Node* head) {
    while (head) {
        cout << head->data << " → ";
        head = head->next;
    }
    cout << "NULL\n";
}

int main() {
    Node* head = nullptr;
    
    // สร้างรายการ: 10 → 2 → 7 → 6 → 85
    push(&head, 85);
    push(&head, 6);
    push(&head, 7);
    push(&head, 2);
    push(&head, 10);
    
    cout << "Linked List: ";
    printList(head);
    
    cout << "Prime nodes: ";
    Node* temp = head;
    while (temp) {
        if (isPrime(temp->data)) cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
    
    cout << "Product of prime nodes = " << productOfPrimeNodes(head) << endl;
    
    // ทดสอบกรณีไม่มีจำนวนเฉพาะ
    Node* head2 = nullptr;
    push(&head2, 10);
    push(&head2, 4);
    push(&head2, 6);
    push(&head2, 8);
    cout << "\nList without primes: ";
    printList(head2);
    cout << "Product = " << productOfPrimeNodes(head2) << endl;
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

Linked List: 10 → 2 → 7 → 6 → 85 → NULL
Prime nodes: 2 7 
Product of prime nodes = 14

List without primes: 8 → 6 → 4 → 10 → NULL
Product = 0

กรณีทดสอบจากโจทย์ต้นฉบับ

อินพุต: 10 20 30 40 50 (สมมติว่าเป็นค่าข้อมูลในโหนด)

จำนวนเฉพาะในรายการ: ไม่มี (10,20,30,40,50 ล้วนไม่ใช่จำนวนเฉพาะ)

ผลลัพธ์: 0

ข้อสังเกต: โจทย์ต้นฉบับกล่าวว่า "Prime nodes are the ones that will have prime values as their count locations" ซึ่งอาจหมายถึง index ที่เป็นจำนวนเฉพาะ (ตำแหน่งที่ 2, 3, 5, 7...) แต่โค้ดตัวอย่างจริงๆ ตรวจสอบค่า data ว่าเป็นจำนวนเฉพาะ สองวิธีให้ผลลัพธ์ต่างกัน

ความซับซ้อนของอัลกอริทึม

• เวลา: O(N × √M) โดย N = จำนวนโหนด, M = ค่าสูงสุดในโหนด
• พื้นที่: O(1) ไม่รวม stack ของการเรียกฟังก์ชัน isPrime

การป้องกัน Overflow

ใช้ long long (64-bit) สำหรับผลคูณ หากข้อมูลใหญ่มาก ควรใช้ Big Integer library หรือ modulo arithmetic