[Haskell-cafe] puzzle: prove this floorSqrt correct

[Remi Turk]

On Thu, Aug 12, 2004 at 09:01:03PM +0200, Henning Thielemann wrote:
> 
> On Thu, 12 Aug 2004, Remi Turk wrote:
> > I usually (each time I urgently need to calculate primes ;)) use
> > a simple intSqrt = floor . sqrt . fromIntegral
> > (which will indeed give wrong answers for big numbers)
> 
> If I urgently need factors of an integer I check "factor*factor > n"
> rather than "factor > intSqrt n". :-]

but you'll have to (^2) once every "iteration".
The following code only has to sqrt once.
Oh, the joy of premature optimization. Or even premature coding ;)

-- Will lie when given stupid questions
isPrime 1   = False
isPrime 2   = True
isPrime n   = not $ any (n`isDivBy`) (2:[3,5..intSqrt n])
    where
        n `isDivBy` d   = n `rem` d == 0
        intSqrt         = floor . sqrt . fromIntegral

-- 
Nobody can be exactly like me. Even I have trouble doing it.