mpirを使ってウィルソンの定理を計算する

ウィルソンの定理は $p$ が素数ならば

$\begin{align} (p-1)! \equiv =-1(mod p) \end{align}$

が成り立つ定理である。今回はwikipediaにある表をmpirを用いて計算した。

	#include <iostream>
	#include <mpir.h>

	mpz_ptr exponentiation(int, int);
	mpz_ptr facctorial(int);

	int main() {
	mpz_t num;
	mpz_init(num);

	mpz_t r;
	mpz_init(r);

	mpz_t d;
	mpz_init(d);

	mpz_set_str(d, "2", 10);

	int N = 10;

	for (int i = 2; i < N; i++) {
	mpz_set(num, facctorial(i-1));
	mpz_mod(r,num, d);
	mpz_add_ui(d, d, 1);
	std::cout << r << std::endl;
	}

	mpz_clear(num);
	mpz_clear(r);
	mpz_clear(d);
	}


	mpz_ptr exponentiation(int n, int loop) {
	mpz_t expnum;
	mpz_init(expnum);
	mpz_set_str(expnum, "1", 10);

	for (int i = 0; i < loop; i++) {
	mpz_mul_ui(expnum, expnum, n);
	}
	return expnum;
	}
	mpz_ptr facctorial(int k) {
	mpz_t sum;
	mpz_init(sum);
	mpz_set_str(sum, "1", 10);

	for (int i = 1; i <= k; ++i)
	{
	mpz_mul_ui(sum, sum, i);
	}
	return sum;
	}

view raw Wilson's theorem hosted with ❤ by GitHub