
/* primtest.q: optimized prime test example, contributed by Tim Haynes */

import hdict;

def HASH = ref emptyhdict;

hashed F X	= get HASH!(F,X) if member (get HASH) (F,X);
		= put HASH (update (get HASH) (F,X) Y) || Y
		    where Y = F X otherwise;

h_primes N	= [2] if N=2;
		= [2,3] if N=3;
		= [2,3|filter isprime [5,7..N]] otherwise;

primes		= hashed h_primes;

h_isprime N	= not (any ((=0).(N mod))) (primes (intsqrt N));

isprime N	= hashed h_isprime N;
