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!