C++で単一リンクリスト内のすべての素数ノードの積を求める方法

単一リンクリストが与えられたとき、値が素数になっているノードをすべて見つけ出し、それらの値の積を計算して出力するのが本稿のテーマです。ここで「素数ノード」とは、データ部分に素数を格納しているノードを指します。

入力例

85 → 6 → 7 → 2 → 10

出力例

14

説明

リストを先頭から順に調べると、85 は 5×17 に分解できるため素数ではなく除外されます。6 も 2×3 であり除外、続く 7 は素数なので採用、2 も素数なので採用、最後の 10 は 2×5 であるため除外されます。したがって積は 7 × 2 = 14 となります。

解決のためのアプローチ

• node 型の一時ポインタ（temp など）を用意します。

• そのポインタを、ヘッドポインタが指す先頭ノードに設定します。

• temp を temp→next へ進めながら、各ノードの値が素数かどうかを判定していきます。

• 値が素数であれば、product = product × (temp→data) を実行して積を更新します。

• 素数でなければ何もせず、次のノードへ進みます。

• リストの末尾に到達したら、product 変数の最終値を出力します。

アルゴリズム

Start
Step 1 → リストに挿入するノードの構造体を作成
    struct node
        int data;
        node* next
    End
Step 2 → ノードをリストに挿入する関数を宣言
    void push(node** head_ref, int data)
        Set node* newnode = (node*)malloc(sizeof(struct node))
        Set newnode→data = data
        Set newnode→next = (*head_ref)
        Set (*head_ref) = newnode
    End
Step 3 → 素数かどうかを判定する関数を宣言
    bool isPrime(int data)
        IF data <= 1
            return false
        End
        IF data <= 3
            return true
        End
        IF data % 2 == 0 || data % 3 == 0
            return false
        Loop For int i = 5 and i * i <= data and i = i + 6
            IF data % i == 0 || data % (i + 2) == 0
                return false
            End
        End
        return true
Step 4 → 積を計算する関数を宣言
    void product(node* head_ref)
        set int product = 1
        set node* ptr = head_ref
        While ptr != NULL
            IF (isPrime(ptr→data))
                Set product *= ptr→data
            End
            Set ptr = ptr→next
        End
        Print product
Step 5 → main() 内での処理
    node* head = NULL を宣言
    Call push(&head, 10)
    Call push(&head, 2)
    Call product(head)
Stop

なお、isPrime 関数では「6k±1 法」という最適化手法を採用しています。2 と 3 の倍数をあらかじめ除外した上で、5 から始めて 6 ずつ増やしながら i と i+2 の両方で割り切れるかを確認することで、平方根 O(√n) の範囲で効率よく素数判定が可能になります。

C++コード例

#include <bits/stdc++.h>
using namespace std;
// ノードの構造体
struct node{
    int data;
    node* next;
};
// ノードを挿入する関数
void push(node** head_ref, int data){
    node* newnode = (node*)malloc(sizeof(struct node));
    newnode→data = data;
    newnode→next = (*head_ref);
    (*head_ref) = newnode;
}
// 数が素数かどうかを判定する関数
bool isPrime(int data){
    if (data <= 1)
        return false;
    if (data <= 3)
        return true;
    if (data % 2 == 0 || data % 3 == 0)
        return false;
    for (int i = 5; i * i <= data; i = i + 6)
        if (data % i == 0 || data % (i + 2) == 0)
            return false;
    return true;
}
// 素数ノードの積を求める関数
void product(node* head_ref){
    int product = 1;
    node* ptr = head_ref;
    while (ptr != NULL){
        if (isPrime(ptr→data)){
            product *= ptr→data;
        }
        ptr = ptr→next;
    }
    cout << \"連結リスト内のすべての素数ノードの積 = \" << product;
}
int main(){
    node* head = NULL;
    push(&head, 10);
    push(&head, 2);
    push(&head, 7);
    push(&head, 6);
    push(&head, 85);
    product(head);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

連結リスト内のすべての素数ノードの積 = 14

計算量について

リンクリストの長さを n、ノードが取りうる最大値を m とすると、リスト全体の走査に O(n)、各ノードの素数判定に O(√m) が必要となるため、全体の時間計算量は O(n√m) となります。補助的な領域はポインタ 1 個分だけで済むため、空間計算量は O(1) です。