はじめに

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

この記事の対象者

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

前提知識

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

実装

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

実際のコード

main.py

from factorizer import factorize

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

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);
}

解説

インクルードと定義

#include <Python.h>
#include <math.h>

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

factorize 関数

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を発生させます。

素因数分解

    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 構造体

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

この部分では、Pythonから呼び出せる関数のリストを定義しています。各要素は、関数の名前、その関数を実行するためのポインタ、引数の形式、関数の説明を示しています。最後の要素は必ず {NULL, NULL, 0, NULL} で終わります。

PyModuleDef 構造体

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

この部分では、拡張モジュールの定義を行っています。PyModuleDef_HEAD_INIT は、この構造体を初期化するためのマクロです。"factorizer" はモジュールの名前を示しています。methods は、先ほど定義した関数のリストです。

PyInit_factorizer 関数

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

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

コンパイル

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

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

終わりに

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