Attractive Numbers, Perl

Attractive Numbers

#perl 5.22.1

%isPrime=(2=>3,3=>5,5=>7,7=>11,11=>-1,largest=>11);
for (1..1000){
  primeFactors($_)
}

sub primeFactors{
   my $wn=$number=shift;
   my @factorsList=();
   my $test=2; $limit=sqrt($wn+1);
   while ($test < $limit){
     if  ($wn % $test){
         $test=$isPrime{$test};
     }
     else{
      push @factorsList,$test;
      storePrime($test);
      $wn=$wn/$test;
      $limit=sqrt($wn+1)      
     }
   }
   push @factorsList,$wn;
   if (scalar @factorsList == 1){
      print "$number is prime\n";
      storePrime($number);
   }
   else{
     print "$number   :factors are ", join ",",@factorsList,($isPrime{scalar @factorsList})? "and is attractive\n":"\n" 
     };
   
  sub storePrime{
    my $p=shift;
    if($p>$isPrime{largest}){
          @isPrime{$p,$isPrime{"largest"},"largest"}=(-1,$p,$p);
      }
  }
   
}

__DATA__
Stash in a Hash

Calling a function that yields a consistent result does provide an oprtunity for saving processing power.  One could remeber the reults, and bypass the computation altogether, retrieving the results from our store. In doing so one sacrifices space (for storing results) to achive better performance. But having a function that 1) checks if a there has been a prior call with the samae parameters, if so retrieve results of the operation,  OTHERWISE   2) store the results for future retrieval itself takes up processing time.  Thus the difference is not always noticeable for infrequently called functions.

a function that derives prime factors is one such processing task.
1) one could sequentially try test factors incrementally up to reasonable limit (sqrt(N)+1), dividing by factors (which will automatically be prime) discovered, and reducing the limit at each discovery of a factor.
2) One could store prime numbers discovered, in a hash and only test these incrementally.  Instead of incrementing the test factors, we could test the next available prime factor (stored in a hash).  If no prime factor, this could be stored in that hash of potential prime factors.
3) one could store prime numbers and previously discovered prime factors storing the results in an array

Lets try each of these and chart the results for varying sizes of inputs:-

Where it makes a significant difference is during large recursive procedures. The leornado function (and other similar functions like fibonnaci series can be such procedures).  These appear to require quadratically more


run \| edit \| history \| help	0