Diary over Finite Fields

515ひかるが書き溜めたメモとコラムと雑記

なんとなく Legendre 記号を計算したくなったので下準備をした

なんとなく, Legendre 記号を計算したくなった. 当然手計算ではなくなんかプログラムを書こうと思ったわけである.

しかし, 当たり前だが標数素数なので素数のリストを作る必要がある. そこで簡単に作ってみた.

#include <iostream>
using namespace std;

int main(int argc, char const* argv[])
{
    int const SIZE = 1000000;
    int const NOTPRIME = 0, PRIME = 1;
    int numbers[SIZE];
    int i, j;
    // 0 と 1 は素数ではない.
    numbers[0] = NOTPRIME;
    numbers[1] = NOTPRIME;
    for(i = 2; i < SIZE; i++) numbers[i] = PRIME;
    for(i = 2; i * i < SIZE; i++)
    {
        for(j = 2; i * j < SIZE; j++)
        {
            numbers[j * i] = NOTPRIME;
        }
    }
    for(i = 1; i < SIZE; i++)
    {
        if(numbers[i] == PRIME) cout << i << endl;
    }
    return 0;
}

解説不要かと思うが, エラトステネスのふるいである. C++ で書いたことにも特に理由はない.

あとはこいつの出力を保存. 素数がいつでも参照できるぞ(?).

./a.out > prime

肝心の Legendre 記号の計算は与えられた数が素数かどうかを判定することが必要(なはず)なので, こういうデータが必要なはず. 根拠はあまりない.

しかし特にデバッグとかしてないけどこれで合ってるよね……? 大学の講義でもやる話だと思うので間違ってたら恥ずかしいぽよ~