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/perluse strict;use warnings;use 5.010;#This array will contian the results of the factorizationour @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 happensfor(1..1000) {  my $num = $_;  factorize($num,getPrimeFactors($num));  printResults($num);  @result = ();}Sample output:983 = 983984 = 2 x 2 x 2 x 3 x 41985 = 5 x 197986 = 2 x 17 x 29987 = 3 x 7 x 47988 = 2 x 2 x 13 x 19989 = 23 x 43990 = 2 x 3 x 3 x 5 x 11991 = 991992 = 2 x 2 x 2 x 2 x 2 x 31993 = 3 x 331994 = 2 x 7 x 71995 = 5 x 199996 = 2 x 2 x 3 x 83997 = 997998 = 2 x 499999 = 3 x 3 x 3 x 371000 = 2 x 2 x 2 x 5 x 5 x 5
Prime factorization of numbers up to 1000
primes;perl
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);