Prime-Factorization(素因数分解) (math/primefact.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-10-06 03:54:40+09:00

なにこれ

素因数分解をする．

関数

• primefact(x)： x を素因数分解した結果を vector<pair> で返す． 各要素について，first に素因数，second に冪指数を格納する． x が $1$ 以下の場合，空の配列を返す．

計算量

• $O(\sqrt x)$

Verified with

• test/aoj_2932.cpp
• test/aoj_NTL_1_A_primefact.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

vector<pair<long long, int>> primefact(long long x) {
	vector<pair<long long, int>> res;

	for(long long i = 2; i * i <= x; i++) {
		if(x % i) continue;

		int ex = 0;
		while(x % i == 0) {
			x /= i;
			ex++;
		}
		res.emplace_back(i, ex);
	}

	if(x > 1) res.emplace_back(x, 1);

	return res;
}

#line 2 "math/primefact.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

vector<pair<long long, int>> primefact(long long x) {
	vector<pair<long long, int>> res;

	for(long long i = 2; i * i <= x; i++) {
		if(x % i) continue;

		int ex = 0;
		while(x % i == 0) {
			x /= i;
			ex++;
		}
		res.emplace_back(i, ex);
	}

	if(x > 1) res.emplace_back(x, 1);

	return res;
}

Back to top page