Prime factorization of numbers up to 1000

Question

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

Answer 1

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);