【Python】C/C++拡張で素因数分解をしてみる

# はじめに

CPythonのC拡張を使って素因数分解する方法を紹介します。

## この記事の対象者

- ある程度PythonとCの知識があり、PythonのC拡張を使ってみたい。

## 前提知識

- 基本的なPython/Cの記法と仕様を理解している

# 実装

Cで書かれたコードをコンパイルしてPython側で呼び出すので`main.py`と`factorizer.c`のふたつのファイルを用意してください。

## 実際のコード

```python: main.py
from factorizer import factorize

print(factorize(11111111111111111)) # [2071723, 5363222357]
```

```diff_c: factorizer.c
#include <Python.h>
#include <math.h>

static PyObject* factorize(PyObject* self, PyObject* args) {
    long num;
    if (!PyArg_ParseTuple(args, "l", &num)) {
        return NULL;
    }

    if (num <= 0) {
        PyErr_SetString(PyExc_ValueError, "Input must be a positive integer");
        return NULL;
    }

    PyObject* factor_list = PyList_New(0);

    while (num % 2 == 0) {
        PyList_Append(factor_list, PyLong_FromLong(2));
        num /= 2;
    }

    for (long i = 3; i * i <= num; i += 2) {
        while (num % i == 0) {
            PyList_Append(factor_list, PyLong_FromLong(i));
            num /= i;
        }
    }

    if (num > 2) {
        PyList_Append(factor_list, PyLong_FromLong(num));
    }

    return factor_list;
}

static PyMethodDef methods[] = {
    {"factorize", factorize, METH_VARARGS, "Factorize a number"},
    {NULL, NULL, 0, NULL}
};

static struct PyModuleDef module = {
    PyModuleDef_HEAD_INIT,
    "factorizer",
    NULL,
    -1,
    methods
};

PyMODINIT_FUNC PyInit_factorizer(void) {
    return PyModule_Create(&module);
}
```

## 解説

### インクルードと定義
```c
#include <Python.h>
#include <math.h>
```
この部分では、Pythonの拡張機能を使用するために必要なヘッダーファイル `<Python.h>` をインクルードしています。また、後で使用する数学関数を利用するために `<math.h>` もインクルードしています。

### factorize 関数
```diff_c
static PyObject* factorize(PyObject* self, PyObject* args) {
    long num;
    if (!PyArg_ParseTuple(args, "l", &num)) {
        return NULL;
    }

    if (num <= 0) {
        PyErr_SetString(PyExc_ValueError, "Input must be a positive integer");
        return NULL;
    }
```
この部分では、`factorize` 関数が定義されています。この関数は、Pythonから呼び出される際に使用されます。関数の引数として、`PyObject* self` と `PyObject* args` が渡されます。`self` はメソッドが属するオブジェクト自体を表し、`args` は関数に渡された引数を表します。

`PyArg_ParseTuple` 関数は、Pythonから渡された引数をパースしてCの変数に格納します。ここでは、"l" フォーマット文字列を使用して、整数値を表す引数を受け取り、その値を `num` 変数に格納しています。もし `PyArg_ParseTuple` が失敗した場合（例えば、引数が整数ではない場合）、`NULL` を返しています。

もし `num` が 0 以下のとき、`ValueError`を発生させます。

### 素因数分解
```c
    PyObject* factor_list = PyList_New(0);

    while (num % 2 == 0) {
        PyList_Append(factor_list, PyLong_FromLong(2));
        num /= 2;
    }

    for (long i = 3; i * i <= num; i += 2) {
        while (num % i == 0) {
            PyList_Append(factor_list, PyLong_FromLong(i));
            num /= i;
        }
    }

    if (num > 2) {
        PyList_Append(factor_list, PyLong_FromLong(num));
    }
```
この部分では、与えられた整数 `num` を素因数分解しています。`factor_list` という新しいリストオブジェクトを作成し、素因数を格納します。

まず、2で割り切れるだけ割っていきます。次に、3以上の奇数で割り切れるだけ割っていきます。素因数を見つけるたびに、それを `factor_list` リストに追加しています。

最後に、`num` が2より大きい場合、それ自身も素数である可能性があるので、`factor_list` に追加しています。

~~多分もっといい方法があると思います。~~

### PyMethodDef 構造体
```c
static PyMethodDef methods[] = {
    {"factorize", factorize, METH_VARARGS, "Factorize a number"},
    {NULL, NULL, 0, NULL}
};
```
この部分では、Pythonから呼び出せる関数のリストを定義しています。各要素は、関数の名前、その関数を実行するためのポインタ、引数の形式、関数の説明を示しています。最後の要素は必ず `{NULL, NULL, 0, NULL}` で終わります。

### PyModuleDef 構造体
```c
static struct PyModuleDef module = {
    PyModuleDef_HEAD_INIT,
    "factorizer",
    NULL,
    -1,
    methods
};
```
この部分では、拡張モジュールの定義を行っています。`PyModuleDef_HEAD_INIT` は、この構造体を初期化するためのマクロです。`"factorizer"` はモジュールの名前を示しています。`methods` は、先ほど定義した関数のリストです。

### PyInit_factorizer 関数
```c
PyMODINIT_FUNC PyInit_factorizer(void) {
    return PyModule_Create(&module);
}
```
この部分では、モジュールを初期化するための関数が定義されています。この関数は、Pythonがこのモジュールをロードする際に呼び出されます。`PyModule_Create` 関数を使用して、先ほど定義した `module` を基にモジュールオブジェクトを作成し、それを返しています。

## コンパイル

```bash
gcc -shared -o factorizer.so factorizer.o $(python3-config --ldflags)
```

`gcc(GNU Compiler Collection)`を使ってコンパイルを行い、共有ライブラリファイル(`.so`)として出力します。

# 終わりに

最後まで読んで頂きありがとうございます。不備があれば是非コメントで指摘して下さい。