#! /usr/bin/perl -w
#
# Perl Power Tools - factor
# Greg Hewgill <greg@hewgill.com> 1998-03-01

if (@ARGV) {
  foreach $n (@ARGV) {
    factor($n);
  }
} else {
  while (<>) {
    chomp;
    factor($_);
  }
}

sub factor {
  my $n = $_[0];
  if ($n < -2147483648 || $n > 2147483647) {
    print "'$n' is not a valid integer\n";
    return;
  }
  print "$n:";
  if ($n != 0) {
    $n = abs($n);
    if ($n == 1) {
      print " 1";
    } else {
      my $q = sqrt($n);
      foreach $p (primes($q)) {
        if ($n % $p == 0) {
          print " $p";
          $n /= $p;
          last if $n == 1;
          redo;
        }
      }
      if ($n > 1) {
        print " $n";
      }
    }
  }
  print "\n";
}

sub primes {
  my $n = $_[0];
  my @p = (0..$n);
  $p[1] = 0;
  foreach $p (@p) {
    if ($p[$p]) {
      $x = $p * 2;
      while ($x <= $n) {
        $p[$x] = 0;
        $x += $p;
      }
    }
  }
  return grep $_, @p;
}