C言語で素因数分解

C言語で素因数分解するプログラムを作ってみました。

方法

1. ユーザから2以上の整数(num)を入力してもらう
2. 偶数の素数が2のみであることを利用し、numを2で割っていく
3. 2以外の素数は全て奇数なので、入力された整数を3以上 sqrt(num)（2でnumは奇数となっている）以下の奇数で割る

割る数が、3以上 sqrt(num) 以下である理由

自然数nが素数でないとき、nの素因数をk (k <= sqrt(n)) とすると、必ず sqrt(n) <= n/k となります（等号成立条件は n=k^2）。割る数と商の大小がnの平方根前後で反転することから、平方根以降の数については約数であるかを調べる必要がないのです。
...うーん、上手く説明できない。

実装例

soinsu.c

#include <stdio.h>
#include <math.h>

int inputNum(void){
    int num = 0;
    while (1){
        printf("素因数分解したい整数を入力：");
        scanf("%d", &num);
        if (num < 2)
            printf("2以上の整数にしてください\n\n");
        else
            break;
    }
    return num;
}

int findFactors(int num){
    int i, cnt = 0;
    printf("%d =", num);
    while (num % 2 == 0){ // 偶数の素数は2のみ
        cnt += 1;
        num /= 2;
    }
    if (cnt > 1)
        printf(" 2^%d *", cnt);
    else if (cnt == 1)
        printf(" 2 *");
    for (i = 3; i <= sqrt(num); i += 2){ // 他の奇数で割っていく
        cnt = 0;
        while (num % i == 0){
            cnt += 1;
            num /= i;
        }
        if (cnt > 1)
            printf(" %d^%d *", i, cnt);
        else if (cnt == 1)
            printf(" %d *", i);
    }
    // ここまでで num は1または sqrt(num) 以下で最大の素数
    if (num != 1) printf(" %d *", num); // 後者なら追記
    printf("\b \n");
    return 0;
}

int main(void){
    int num;
    num = inputNum();
    findFactors(num);
    return 0;
}

実行結果

素因数分解したい整数を入力：90
90 = 2 * 3^2 * 5

素因数分解したい整数を入力：517
517 = 11 * 47