# Prime factorization of numbers up to 1000

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  ## 1 Answer There are a few things which can improve this logic: • In order to find out whether a number n is prime, you only need to go up to sqrt(n), not n/2; that will speed up the prime validation considerably for large numbers. • Also, if you're verifying whether a sequence of numbers are primes, you should store the previous results instead of starting from scratch all the time. The function below calculates the primes from 2-1000, which is a good "pre-processing" step for your function (factorizing is now a matter of traversing only that prime numbers list) Calculate prime numbers from 1..1000: use strict; my @primes; my$i;

for my $i (2..1000) { my$isPrime = 1;
my $sqrt = int(sqrt($i));
for my $j (@primes) { if (($i % $j) == 0) {$isPrime = 0;
last;
}
last if $j >$sqrt;
}
if ($isPrime) { push @primes,$i;
}
}

print join(", ", @primes);

• Would +1 if I had the ability. It is unclear to me how the $j loop can work if you start with an empty @primes array. Won't the loop immediately break and end the program? – Ikram Hawramani Jun 8 '11 at 14:42 • The$j loop at first simply won't loop at all, it will just go to the next line (if \$isPrime), which will be true, and it will add the first element to the prime array. – carlosfigueira Jun 8 '11 at 15:11
• I'd add some small value to the square-root to ensure that floating point rounding won't cause you to skip the last check. – CodesInChaos Aug 17 '15 at 8:34