Re: [q-lang-users] Problem using function "isprime"

[<Dr....@t-...>]

Tim Haynes wrote:
> While we're here, consider this pair of mutually-recursive functions for
> the job, as well:
> 
>     isprime N = not (any ((=0).(N mod))) (primes (intsqrt N)) ;
> 
>     primes N = [2] if  N=2;
>              = filter isprime [2..N] otherwise;
> 
> Not quite as pretty to look at, but I think it may run faster as it only
> uses the primes between 2..intsqrt N rather than all odds, if I read your
> algorithm right...

Hi, Tim! From the algorithm I posted:

 >                    = try_div 3 (intsqrt N) N otherwise;
                                   ^^^^^^^

See? :)

While your algorithm looks quite neat, I doubt that it will be any 
faster, since it uses a list, while the one from the docs is just plain 
tail-recursive number crunching (which has the added benefit that it 
only needs O(1) space). I'm also a bit worried about the recursive 
isprime call, which might slow down things quite a bit if enough members 
of the [2..N] list fail the Miller-Rabin test.

Albert

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikwissenschaft.uni-mainz.de/~ag