なんとなく 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;
}