#include <stdio.h>
#include <stdlib.h>

// 連結リストのノードを定義する構造体
typedef struct Node {
    int data;           // 素因数を格納
    struct Node* next;  // 次のノードへのポインタ
} Node;

// 新しいノードを作成する関数
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("メモリ確保に失敗しました。\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

int main() {
    int n;
    Node* head = NULL; // リストの先頭ポインタ
    Node* tail = NULL; // リストの末尾ポインタ

    printf("正の整数を入力してください: ");
    if (scanf("%d", &n) != 1 || n <= 0) {
        return 1;
    }

    int temp = n;
    for (int i = 2; i * i <= temp; i++) {
        while (temp % i == 0) {
            Node* newNode = createNode(i);
            if (head == NULL) {
                head = newNode; // 最初の要素なら先頭にする
                tail = newNode;
            } else {
                tail->next = newNode; // 末尾に追加
                tail = newNode;
            }
            temp /= i;
        }
    }
    if (temp > 1) {
        Node* newNode = createNode(temp);
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }

    // リストを表示
    printf("%d の素因数分解結果: ", n);
    Node* current = head;
    while (current != NULL) {
        printf("%d", current->data);
        if (current->next != NULL) {
            printf(" * ");
        }
        current = current->next;
    }
    printf("\n");

    // メモリの解放
    current = head;
    while (current != NULL) {
        Node* nextNode = current->next;
        free(current);
        current = nextNode;
    }

    return 0;
}