#!/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; }