Top / 総当たり
HTML convert time: 0.030 sec.

総当たり

Last-modified: 2015-03-21 (土) 13:18:42

素因数分解を行うプログラムの一つに、2から順に割っていくという方法があります。次に書くプログラムでは、打ち込まれた数に対して「2,3,4,5,6...」というように割っていきます。4や6で割ってしまっていいのかと思うかもしれませんが、すでに2や3で割っているのでとくに問題はありません。

/*                         */
/*   nomal factorization   */
/*                         */

#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;

int main()
{
	__int64 X;
	cout << "\n素因数分解" << "\n    MAX:9223372036854775807" << endl;
	cout << "      X=" ;
	cin >> X;
	cout << "\n        " << X << " = ";

	clock_t start = clock();

	__int64 quo = X;

	for (int i = 2; i <= sqrt(X); i++){
		int ruijo = 0;
		if (quo%i == 0){
			cout << i;
			while (quo%i == 0){
				ruijo++;
				quo = quo / i;
			}
			if (ruijo == 1){
				cout << " ";
			}
			if (ruijo >= 2){
				cout << "^" << ruijo << " ";
			}
			if (quo == 1){
				break;
			}
		}
	}
	if (quo >= sqrt(X)){
		if (quo == X){
			cout << "Prime Number";
		}
		else{
			cout << quo;
		}
	}
	cout << endl;

	clock_t end = clock();
	cout << "time=" << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;
	return 0;
}

<計算結果>
 適当に数値を入れて計算にかかる時間を調べたいと思います。

  X : time (素因数分解の結果)
  123456787654321 : 0.001s  (11^2*73^2*101^2*137^2)
  12345678987654321 : 0.014s  (3^4*37^2*333667^2)
  100000000000000000 : 0.001s  (2^17*5^17)
  1234567890987654321 : 25.278s  (3^2*19*928163*1111211111)
  1111211111 : 0.001s  (Prime Number)

この結果から素因数が小さい数で成り立っている数の素因数分解は桁数に関係なく速いが、桁数が大きく、大きな素因数を含んでいるときには計算時間が多くかかってしまうことがわかりました。