# factorize.pl
# 内容 :　素因数分解のプログラム
# Copyright (c) 2002-2011 Mitsuo Minagawa, All rights reserved.
# (minagawa@fb3.so-net.ne.jp)
# 使用方法 : c:\>perl factorize.pl
#   
open(IN1,"in1.txt");    
open(OUT1,">out1.txt");        

#   
#定数の設定 
#   
@table    =    (1,2,2,4);    
while    ($number    =    <IN1>)    {    
    $w_divisor  =    0;    # 割る数の保存した値
    $w_power    =    0;    # 保存した割る数が何乗なのかを示す値
    chomp($number);    
    print    OUT1    "$number = ";    
    $divisor    =    2;        #割る数    
    $index      =    0;        #インデックス    
#   
#素因数分解 
#   
    while        ($number    >    $divisor)      {    
#   
#割られる数÷割る数の余り   
#   
                $surplus    =    $number        %    $divisor;    
#   
#割り切れたとき 
#   
        if          ($surplus   ==    0)            {
                    $number     /=    $divisor;
# 最初の割る数
            if      ($w_divisor ==    0)            {
                    $w_divisor  =    $divisor;
                    $w_power    =    1;
            }    
# 同じ割る数が連続したとき
            elsif   ($divisor   ==    $w_divisor)   {
                    $w_power++;
            }    
# 割る数が変わったとき
            elsif   ($divisor   !=    $w_divisor)   {
# 保存した割る数が1乗だったとき
                if  ($w_power   ==    1)            {
                    print    OUT1    "$w_divisor × ";    
                }    
# 保存した割る数が2乗以上だったとき
                else                                {
                    print    OUT1    "$w_divisor^$w_power × ";    
                }    
                $w_power    =    1;
                $w_divisor  =    $divisor;
            }    
        }    
#   
#割り切れないとき   
#   
        else                                        {    
                $divisor    +=    $table[$index];    
            if  ($index     ==    3)                {    
                $index--;    
            }    
            else                                    {    
                $index++;    
            }    
        }    
    }    
# 保存した割る数が何もない(素数)のとき
    if      ($w_divisor    ==    0)                 {
            print    OUT1    "$number\n";    
    }    
# 保存した割る数の乗数が1乗のとき
    elsif   ($w_power    ==    1)                   {
            print    OUT1    "$w_divisor × $number\n";    
    }
# 最後の割る数と保存した割る数が同じ(同じ割る数がもう1乗増える)とき
    elsif   ($w_divisor    ==    $number)           {
            $w_power++;
            print    OUT1    "$w_divisor^$w_power\n";    
    }    
# 最後の割る数と保存した割る数が異なり、保存した割る数の乗数が2乗以上とき
    else                                            {
            print    OUT1    "$w_divisor^$w_power × $number\n";    
    }    
}    
close(IN1);
close(OUT1);
    

111111111111
82944
580608
8616460799
37
    

111111111111 = 3 × 7 × 11 × 13 × 37 × 101 × 9901
82944 = 2^10 × 3^4
580608 = 2^10 × 3^4 × 7
8616460799 = 89681 × 96079
37 = 37