2
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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);
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Ikram Hawramani Jun 8 '11 at 14:42
  • \$\begingroup\$ 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. \$\endgroup\$ – carlosfigueira Jun 8 '11 at 15:11
  • \$\begingroup\$ 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. \$\endgroup\$ – CodesInChaos Aug 17 '15 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.