素因数分解コンソール

prime-factrize.cpp

#include <iostream>
#include <gmpxx.h>

using namespace std;

mpz_class GCD (mpz_class m, mpz_class n) {
	mpz_class t;
	while (n != 0) {
		t = m;
		m = n;
		n = t % n;
	}
	return m;
}

mpz_class f (mpz_class s, mpz_class n) {
	srand(s.get_ui());
	return rand() % n;
}

mpz_class factorize (mpz_class n) {
	mpz_class x = 2;
	mpz_class y = 2;
	mpz_class d = 1;
	while (d == 1) {
		x = f(x, n);
		y = f(f(y, n), n);
		d = GCD(abs(x - y), n);
	}
	if (d == n) {
		return 0;
	}
	return d;
}

int main() {
	mpz_class a;
	string buf;
	cout << "Factorize(n) >> ";
	while(cin >> buf) {
		a.set_str(buf, 10);
		cout << factorize(a).get_str() << endl;
		cout << "Factorize(n) >> ";
	}
}