I was reading Mathematics: A Very Short Introduction and it mentioned prime factorization. Being a curious person I had to write my own implementation in Perl.
This program outputs the prime factorization of the numbers between 0 and 1001.
I don't like listing all of my subroutines before everything else, but I'm not sure what would be a better alternative.
Also, I remember seeing somewhere a non-bruteforce way of discovering whether a number is a prime. Does anyone have any ideas? I'm a beginner/intermediate Perl programmer and would appreciate suggestions on improving my technique.
#!/usr/bin/perl
use strict;
use warnings;
use 5.010;
#This array will contian the results of the factorization
our @result;
sub factorize {
my($num,$factorsRef) = @_;
# If the only factor is 1, it is a prime number
# return the number itself since primes don't
# factorize in the known universe
if(${$factorsRef}[0] == 1) {
push @result, $num;
return;
}
if($num % ${$factorsRef}[0] == 0) {
push @result, ${$factorsRef}[0];
my $divResult = $num/${$factorsRef}[0];
# If the result of the division is a prime
# we have reached the end of the process
if(isPrime($divResult)) {
push @result, ($divResult);
# If it is not a prime, go down to the
# next level
} else {
factorize($divResult,$factorsRef);
}
# If the number is no longer divisible by the
# current factor, take the factor out so that
# the function can use te next factor
} else {
shift @{$factorsRef};
factorize($num,$factorsRef);
}
}
sub getPrimeFactors {
my $num = shift;
my $counter = 1;
my @primeFactors;
if(isPrime($num)) {
push @primeFactors, 1;
return \@primeFactors;
}
while($counter++ <= ($num / 2)) {
next unless $num % $counter == 0;
push @primeFactors, $counter if(isPrime($counter));
}
return \@primeFactors;
}
sub isPrime {
my $num = shift;
my $limit = $num/2;
for(my $i=2; $i<=$limit ;$i++) {
if ($num%$i == 0) { return 0;}
}
return 1;
}
sub printResults {
my $num = shift;
print $num . ' = ' . shift @result;
print " x $_" for @result;
print "\n";
}
# Where everything happens
for(1..1000) {
my $num = $_;
factorize($num,getPrimeFactors($num));
printResults($num);
@result = ();
}
Sample output:
983 = 983 984 = 2 x 2 x 2 x 3 x 41 985 = 5 x 197 986 = 2 x 17 x 29 987 = 3 x 7 x 47 988 = 2 x 2 x 13 x 19 989 = 23 x 43 990 = 2 x 3 x 3 x 5 x 11 991 = 991 992 = 2 x 2 x 2 x 2 x 2 x 31 993 = 3 x 331 994 = 2 x 7 x 71 995 = 5 x 199 996 = 2 x 2 x 3 x 83 997 = 997 998 = 2 x 499 999 = 3 x 3 x 3 x 37 1000 = 2 x 2 x 2 x 5 x 5 x 5