[Haskell-beginners] Prime number test performance on negative integers

[Francesco Ariis]

Il 11 dicembre 2023 alle 20:24 Folsk Pratima ha scritto:
> Also, the fact that the code runs forever nonetheless is very sad,
> because C equivalent taken from wiki[1] calculates the whole things
> almost immediately. The C code is ultra simplified:
> 
> #include <stdio.h>
> #include <stdint.h>
> int IsPrime(int64_t n)
> {
>     if (n == 2 || n == 3)
>         return 1;
> 
>     if (n <= 1 || n % 2 == 0 || n % 3 == 0)
>         return 0;
> 
>     for (int i = 5; i * i <= n; i += 6)
>     {
>         if (n % i == 0 || n % (i + 2) == 0)
>             return 0;
>     }
> 
>     return 1;
> }
> 
> int main () {
>     printf ("1506491439391566589: %d\n", IsPrime (1506491439391566589));
> }

Let’s implement the algorithm in Haskell, shall we?

    import System.Environment

    isPrimeWiki :: Integer -> Bool
    isPrimeWiki 2 = True
    isPrimeWiki 3 = True
    isPrimeWiki n
        | n <= 1 ||
          rem n 2 == 0 ||
          rem n 3 == 0    = False
    isPrimeWiki n =
        let f i
              | i^2 > n = True
              | rem n i == 0 ||
                rem n (i+2) == 0 = False
              | otherwise = True
        in f 5

    main :: IO ()
    main = do
        [n] <- getArgs
        print $ isPrimeWiki (read n)

then

    f at x270:/tmp/prova$ time ./prime 1506491439391566589
    True

    real    0m0.014s
    user    0m0.001s
    sys     0m0.005s