## Issue

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
```

## Solution

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.

Answered By – AKX

Answer Checked By – Katrina (BugsFixing Volunteer)