Run Code

API

Code Wall

Misc

Feedback

Login

Theme

Privacy

Patreon
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
OSTL prateeshrk
Perl
doctor
Basics
Perl Lang
Challenge 41 Task 1
hash of arrays of arrays
Simple Perl Interview Question
Cheat attractive
Compare Versions