2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

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

Last updated at Posted at 2024-05-01

はじめに

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

この記事の対象者

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

前提知識

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

実装

Cで書かれたコードをコンパイルしてPython側で呼び出すのでmain.pyfactorizer.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* selfPyObject* 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)として出力します。

終わりに

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

2
1
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?