とりあえず Legendre 記号を計算できたっぽい

結局 Jacobi 記号の計算をすることにしたけど, 法とする整数を素数に限ることで事実上 Legendre 記号の計算になっているはずである.

しかし, 正しいかテストなど全くしていない. あと, 素数のリスト prime は昨日のエラトステネスのふるいで作っている.

hikaru515.hatenablog.com

コード

#include<iostream>
#include<string>
#include <fstream>

using namespace std;

int residue(int a, int m);
int first_law(int p);
int second_law(int p);
int jacobi(int a, int p);
bool isprime(int p);

int main(int argc, char const* argv[])
{
	int a, p;
	cout << "法とする素数はなんですか?" << endl;
	cin >> p;
	if(!isprime(p))
	{
		cout << "プログラムを終了します." << endl;
		return 0;
	}
	cout << "整数を適当に入力してください." << endl;
	cin >> a;
	cout << "(" << a << "/" << p << ") =" << jacobi(a, p) << endl;
	return 0;
}

// 第一補充法則
int first_law(int p)
{
	return p % 4 == 1? 1 : -1;
}

// 第二補充法則
int second_law(int p)
{
	return ((p % 8 == 1) || (p % 8 == 7))? 1 : -1;
}

// 相互法則のときの符号
int residue(int a, int m)
{
	return ((a - 1) * (m - 1) / 4 ) % 2 == 0? 1 : -1;
}

// Jacobi 記号の計算
int jacobi(int a, int p)
{
	if(a == 1) return 1;
	if(a % p == 0 ) return 0;
	if(a < 0)  return first_law(p) * jacobi(-a, p);
	if(a % 2 == 0) return second_law(p) * jacobi(a / 2, p);
	else return residue(a, p) * jacobi(p % a, a);
}

// 素数かどうかの判定
bool isprime(int p)
{
	if(p == 2)
	{
		cout << "素数ですが, Legendre 記号は計算できません." << endl;
		return false;
	}
	ifstream ifs("prime");
	string str;

	if(ifs.fail())
	{
		cout << "File do not exists." << endl;
	}
	int a;
	while (getline(ifs, str)) 
	{
		sscanf(str.data(), "%d\n", &a);
		if (a < p) continue;
		if (a > p) break;
		if(a == p)
		{
			cout << p << " は素数です. " << endl;
			return true;
		}
	}
	cout << p << " は素数ではありません." << endl;
	return false;
}