File Coverage

bin/factor

Criterion	Covered	Total	%
statement	59	67	88.0
branch	25	34	73.5
condition	2	5	40.0
subroutine	4	4	100.0
pod			n/a
total	90	110	81.8

#!/usr/bin/perl

=begin metadata

Name: factor
Description: factor a number
Author: Jonathan Feinberg, [e-mail]
Author: Benjamin Tilly, [e-mail]
Contributor: brian d foy, [e-mail]
Contributor: Dana Jacobson, [e-mail]
License: perl

=end metadata

=cut


package PerlPowerTools::factor;

use strict;
$|++;
my @primes = (2, 3, 5, 7, 11);          # None have been tested
my @next_primes = ();                   # Avoid redoing work


my $VERSION = '1.002';

END {
	close STDOUT || die "$0: can't close stdout: $!\n";
	$? = 1 if $? == 255;  # from die
	}

__PACKAGE__->run( \*STDOUT, @ARGV ) unless caller(); # modulino

sub run {
	my( $self, $fh, @numbers ) = @_;
	$fh = *STDOUT unless defined $fh;

	my $old = select $fh;

	if( @numbers ) {
		foreach ( @numbers ) { factor($_) }
		}
	else {
		while (<>) {
			chomp;
			if (/^\s*(\S+)/) {
				factor($1);
				}
			}
		}

	select $old;

	exit 0;
	}

sub factor {
  my $n = shift;
  unless ($n =~ /^\+?\d{1,10}$/ && $n <=  2**32 - 1) {
    warn "$0: `$_' is not a valid positive integer\n";
    return;
  }
  exit 0 if $n == 0;
  print "$n:";
  if ($n == 1) { print "1\n"; return }
  # Start with existing list
  foreach my $prime (@primes) {
    while ($n % $prime == 0) {
      print " $prime";
      $n /= $prime;
    }
  }
  while ($primes[-1] * $primes[-1] < $n) {
    &more_primes(int($n**0.5)+1); # the doubles might come in slightly under, so add 1
    last unless scalar @next_primes;    # Avoid the chance of an endless loop
    foreach my $prime (@next_primes) {
      while ($n % $prime == 0) {
        print " $prime";
        $n /= $prime;
      }
      last if $n < $prime * $prime;
    }
    push @primes, @next_primes;
  }
  if ($n > 1) { print " $n" }
  print "\n";
}

sub more_primes {
  # This adds to the list of primes until it reaches $max
  #      or the square of the largest current prime (assumed odd)
  my $max = shift||32000;
  my $square = $primes[-1] * $primes[-1];
  $max = $square if $square < $max;     # Determine what to find primes to
  my $base = $primes[-1] + 2;           # First possible prime
  $base++ unless $base % 2;             # Make the base odd
  $max-- if $max %2;                    # Make the max odd
  $max = ($max - $base)/2;              # Make $max into a count of odds
  return @next_primes = () if $max < 0; # Sanity check
  my @more = map {0} 0..$max;           # Initialize array of 0's for the
                                        # odd numbers in our range
  shift @primes;                        # Remove 2
  foreach my $p (@primes) {
    my $start;
    if ($base < $p * $p) {
      $start = ($p * $p - $base)/2;     # Start at the square
      if ($max < $start) {              # Rest of primes don't matter!
          last;
      }
    }
    else {                              # Start at first odd it divides
      $start = $base % $p;              # Find remainder
      $start = $p - $start if $start;   # Distance to first thing it divides
      $start += $p if $start %2;        # Distance to first odd it divides
      $start = $start/2;                # Reindex for counting over odd!
    }
    for (my $i = $start; $i <= $max; $i += $p) {
      $more[$i] = 1;
    }
  }
  unshift @primes, 2;                   # Replace 2
  # Read off list of primes
  @next_primes = map {$_ + $_ + $base} grep {$more[$_] == 0} 0..$max;
}


__END__