Run Code

API

Code Wall

Users

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
Please
log in
to post a comment.
PWC 0591
Supriya
Shalu Kumar
taller in front
codeyard
Sanjana 101742
Neha101736
neigh.pl
Hash
Password Validation
Please log in to post a comment.