Re: Unable to Understand grep and hash use for prime no.

[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:

(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.

(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.