KMS07 : C++ 소인수분해, 소수판별, 확장유클리드 알고리즘 소스

KMS07 - 부재 KMS04 - 2

 요즘 좋은 영감이 떠오르질 않네요. 그래서 지난번 KMS06에서 만든 확장유클리드 알고리즘과 여러 소수관련 함수들을 통합한 프로그램을 하나 만들었습니다. 참고로 소수 탐색기는 KMS04에서 만들었는데, KMS04소스 하나에만 500줄을 넘어가서 굳이 합치지는 않았습니다.

사실상 KMS04, KMS06종합인 KMS07이기 때문에 이번에 설명은 따로 하지 않겠습니다.

---

소스

source.cpp

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

namespace GenP_KMS {

#define TRUE	1
#define FALSE	0

#define MAX(x, y)	((x > y) ? (x) : (y))
#define MIN(x, y)	((x < y) ? (x) : (y))

	namespace for_iner_func {
		bool b;
		inline long double nextP(long double N) {
			b = !b;
			return N + ((!b) ? 2 : 4);
		}
	}

	template<typename tera>
	inline tera GCD(tera x, tera y) { return (!y) ? x : GCD(y, fmodl(x, y)); }
	template<typename tera>
	inline tera LCM(tera x, tera y) { return x * y / GCD(x, y); }

	//소수판단 (integ가 소수인가? )
	bool IsPrime(long double integ) {
		for_iner_func::b = true;
		if (!((fmodl(integ, 2)) && (fmodl(integ, 3)))) { return false; }
		for (long double num = 5; num <= sqrtl(integ); num = for_iner_func::nextP(num)) {
			if (!fmodl(integ, num)) { return false; }
		}
		return true;
	}

	//소인수분해
	vector<long double> divPrime(long double integ) {
		for_iner_func::b = true;
		long double ceta = integ;
		vector<long double> beta;
		while (!fmodl(integ, 2)) {
			beta.push_back(2.0);
			integ /= 2.0;
		}
		while (!fmodl(integ, 3)) {
			beta.push_back(3.0);
			integ /= 3.0;
		}
		for (long double num = 5; num <= sqrtl(integ); num = for_iner_func::nextP(num)) {
			while (!fmodl(integ, num)) {
				beta.push_back(num);
				integ /= num;
			}
		}
		if (integ != 1)
			beta.push_back(integ);
		if (!beta.size())
			beta.push_back(ceta);
		return beta;
	}

	// ax + by = GCD(a, b)의 (x, y)근
	pair<long double, long double> EEDA(long double a, long double b) {
		long double alpa1 = 0, alpa = 0;
		long double beta2 = 0, beta1 = 1, beta = 0;
		long double ceta2 = 1, ceta1 = 0, ceta = 0;

		long double A = MAX(a, b);
		long double B = MIN(a, b);
		long double C = fmod(A, B);
		alpa1 = fmodl(A, B);
		ceta1 = -1 * (floorl(A / B));
		while (true) {
			alpa = fmodl(B, alpa1);
			beta = beta2 - (floorl(B / C) * beta1);
			ceta = ceta2 - (floorl(B / C) * ceta1);
			A = B;
			B = C;
			C = alpa;

			if (!fmodl(B, C))
				break;

			alpa1 = alpa;
			beta2 = beta1;
			beta1 = beta;
			ceta2 = ceta1;
			ceta1 = ceta;
		}
		return make_pair(beta, ceta);
	}
}

int main(void) {
	bool V1;
	vector<long double> V2;
	long double P;
	cin >> P;
	V1 = GenP_KMS::IsPrime(P);
	V2 = GenP_KMS::divPrime(P);
	cout << "isPrime :\t" << V1 << endl;
	cout << "divPrime :\t";
	for (int i = 0; i < (V2.size() - 1); i++) {
		cout << V2.at(i) << " * ";
	}
	cout << V2.at(V2.size() - 1) << endl;
	return 0;
}

이상으로 KMS이였습니다. 감사합니다.

---

relation content

확장 유클라디안 알고리즘 : blog.naver.com/tomskang/221760015857

[C++] 확장 유클리드 알고리즘 소스

자작 Tayo algorithm