# 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);	
