#!/usr/bin/perl
use CGI qw(param);
# Compute least prime factor of n
print "Content-type: text/html\n\n";
print "Output
\n";
my $n = param("input");
$n=int($n);
if($n<2){print "Your input n must be an integer bigger than 1.
\n";}
if($n>=1000000000){print "Your input n must be less than 1,000,000,000.
\n";}
if($n>1 && $n<1000000000){
$N=$n;
$p=2;
$i=0;
while($p*$p<=$n){
if($n%$p == 0){
$n=int($n/$p);
if($factor1[$p]==0) {
$i=$i+1;
$factor2[$i]=$p;
$factor1[$p]=$i;}
$factor3[$p]=$factor3[$p]+1;
# print "Chk3: $factor3[$p]\n";
# print "Chk1: $factor1[$p]\n";
# print "Chki: $i\n";
# print "Chk2: $factor2[$i]\n";
# print "$p\n";
}
else {$p=$p+1;}}
if($factor1[$n]==0) {
$i=$i+1;
$factor2[$i]=$n;
$factor1[$n]=$i;}
$factor3[$n]=$factor3[$n]+1;
$j=2;
$str=$factor2[1] . "^" . $factor3[$factor2[1]];
while($j<=$i) {
$str=$str . " x " . $factor2[$j] . "^" . $factor3[$factor2[$j]];
$j=$j+1;}
print "Here is the prime factorization of $N:
\n";
print "$N = $str\n";
}
print "\n";