Primality test Python C extension is slower than pure Python-CodePudding

I've implemented a 6k -1 primality test function both in a C extension and pure Python code but seems pure Python code is much faster! is there something wrong with my C code or something else? I also compiled a similar test in pure C with the is_prime function, and its execution time was the same as the C extension (almost 2sec)

primemodule.c

#define PY_SSIZE_T_CLEAN
#include "Python.h"

int is_prime(int n)
{
    int i;

    if (n <= 3)
        return (n > 1);
    if (n % 2 == 0 || n % 3 == 0)
        return (0);
    i = 5;
    while ((i * i) <= n)
    {
        if (n % i == 0 || n % (i   2) == 0)
            return (0);
        i  = 6;
    }
    return (1);
}

static PyObject *prime_isprime(PyObject *self, PyObject *args)
{
    int n;

    if (!PyArg_ParseTuple(args, "i", &n))
        return (NULL);
    if (is_prime(n))
        Py_RETURN_TRUE;
    Py_RETURN_FALSE;
}

static PyMethodDef prime_methods[] = {
    {"is_prime", prime_isprime, METH_VARARGS, "Check if a number is prime"},
    {NULL, NULL, 0, NULL}};

static struct PyModuleDef prime_module = {
    PyModuleDef_HEAD_INIT,
    "prime",
    NULL,
    -1,
    prime_methods};

PyMODINIT_FUNC PyInit_prime(void)
{
    return (PyModule_Create(&prime_module));
}

py_test.py

import time

MAX_INT = 2147483647

def is_prime(n: int) -> bool:
    if n <= 3:
        return n > 1
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i ** 2 <= n:
        if n % i == 0 or n % (i   2) == 0:
            return False
        i  = 6
    return True

t1 = time.process_time()

for i in range(MAX_INT - 100, MAX_INT):
    is_prime(i)
        
print(time.process_time() - t1, "seconds")

c_test.py

import time
import prime

MAX_INT = 2147483647

t1 = time.process_time()

for i in range(MAX_INT - 100, MAX_INT):
    prime.is_prime(i)
        
print(time.process_time() - t1, "seconds")

python c_test.py

2.078125 seconds

python py_test.py

0.03125 seconds

timecmd.bat a.exe

2.13 seconds

CodePudding user response：

I think your C implementation is buggy regarding integer overflows and signedness and ends up in a bigger loop than the Python version.

Changing the parameter type to unsigned int (and i too, since otherwise that's a compiler warning):

static int is_prime(unsigned int n)
{
    unsigned int i;

    if (n <= 3)
        return (n > 1);
    if (n == 2 || n == 3)
        return (1);
    if (n % 2 == 0 || n % 3 == 0)
        return (0);
    i = 5;
    while ((i * i) <= n)
    {
        if (n % i == 0 || n % (i   2) == 0)
            return (0);
        i  = 6;
    }
    return (1);
}

makes it (anecdotally, on my machine, approximately) 37 times faster than the Python implementation.