// 素因数分解のプログラム
#include <stdio.h>

int main(void)
{
    int j = 2; //割る数
    int n = 3072; //割られる数（n>2）
    int cnt = 0; //素因数分解できた回数

    printf("%d を素因数分解します。\n", n);

    do {
        if (n%j == 0) { // 素因数分解できた
            printf("%3d) %d\n", j, n);
            n = n / j;
            cnt++;
        }
        else { // 素因数分解できなかった
            if (n == 1) break;
            j++;
        }
    } while (n >= j*j);
    printf("     %d\n", n);

    if (cnt == 0) {
        puts("The number is prime number.");
    } else {
        printf("The number is a product of %d prime numbers.\n", (cnt+1));
    }

    // 素因数の最大値は n です。

    return 0;
}