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

[Folsk Pratima]

>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
Ahem,

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int IsPrime(int64_t n, char **msg)
{
    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) {
            sprintf (*msg, "divisible by %d", i);
            return 0;
        }
        if (n % (i + 2) == 0) {
            sprintf (*msg, "divisible by %d", i + 2);
            return 0;
        }
    }

    return 1;
}

int main () {
    char *msg[1];
    msg[0] = malloc (sizeof (char) * 128);
    sprintf (msg[0], "success");
    int res;
    int64_t num;
    char numstr[] = "1506491439391566589";
    num = 1506491439391566589;
    res = IsPrime (num, msg);
    printf ("%s: %d: %s\n", numstr, res, msg[0]);
}

tells me the number is divisible by 13 and is *not* primal. The
qalculate tells me pretty much the same!