note
anonymized user 468275
Finding out if a number is prime has the typical algorithm of testing all integers less than the square root of the number for whether they are a factor (and of course eliminating a perfect square). The author is trying to trade off storage for execution time by saving previous calculations as a hash (key = number, value = boolean for whether prime). I have some thoughts:<p> (1) only prime factors need to be tested as factors and so test factors (all of them used per test) should also have their results kept in the lookup, so the lookup storage belongs to the function 'is_prime' (could be a package variable) rather than held at the scope shown in the snippet. <p>(2) hash access slows disproportionately whereas this lookup could just be an array. That array could be packed down to one bit per element for the most efficient storage, given that it has only boolean values. Lookup (and registration) can be achieved without unpacking from that using bit operators such as '<<' and '&', thereby winning on processing as well as storage. <!-- Node text goes above. Div tags should contain sig only -->
<div class="pmsig"><div class="pmsig-468275">
<p><i>One world, one people</i>
</div></div>
1137324
1137324