#!/usr/bin/perl

use strict;
use warnings;

for my $startnum ( @ARGV )
{
   print "factors of $startnum: ";

   my $number = $startnum;
   my %factors;
   my $prime = 0;

   FACTORS: while ( my $factor = smallest_factor( $number ) )
   {
      $factors{ $factor }++;
      if ( $factor == $startnum )
      {
         # only factor is self
         $prime = 1;
         last FACTORS;
      }

      $number = $number / $factor;
      last FACTORS if ( $number < 2 );
   }

   if ( $prime )
   {
      print "No factors, prime number.";
   } else {
      print join( ", ",
                  map { $_ . (( $factors{$_} > 1 ) ?
                     "^" . $factors{$_} : "" ) }
                  sort { $a <=> $b } keys %factors );
   }

   print "\n";
}

sub smallest_factor 
{
   my $number = shift;

   my $factor = sieve( $number, 100, 1 );

   return $factor if ( $factor );

   my $upper = int( sqrt $number );
   return sieve( $number, $upper );
}

sub sieve
{
   # This creates a vec() Sieve of Eratosthenes,
   # which is a vector where bit n is 0 if n is
   # prime.  It creates a sieve up to $upper, then
   # checks each prime from 1 to $upper against our
   # $number for factors.

   my $number = shift;
   my $upper = shift;
   my $fail = shift || 0;
   my $sieve = "";

   # pre-inflate sieve to avoid re-occuring 
   # allocation costs:
   vec( $sieve, $upper, 1 ) = 0;

   GUESS: for ( my $guess = 2;
                $guess <= $upper;
                $guess++ )
   {
      next GUESS if vec( $sieve, $guess, 1 );

      # otherwise, this number is a prime

      # check if it divides $number
      unless ( $number % $guess )
      {
         return $guess;
      }

      # add multiples of this prime to our sieve
      for ( my $mults = $guess * $guess;
            $mults <= $upper;
            $mults += $guess )
      {
         vec( $sieve, $mults, 1 ) = 1;
      }
   }
   return 0 if $fail;
   return $number;
}