Factors 構造体

エラトステネスの篩を利用した高速な素因数分解・約数列挙（Osa_k 法） https://osak.jp/diary/diary_201310.html#20131017 https://qiita.com/drken/items/3beb679e54266f20ab63 [詳解]

#include "factors.hpp"

公開メンバ関数
	Factors (int n)
	前計算
vector< pair< int, int > >	get_prime_factors (int n)
	n を素因数分解する
vector< int >	get_divisors (int n)
	n の約数を返す

詳解

エラトステネスの篩を利用した高速な素因数分解・約数列挙（Osa_k 法） https://osak.jp/diary/diary_201310.html#20131017 https://qiita.com/drken/items/3beb679e54266f20ab63

factors.hpp の 6 行目に定義があります。

構築子と解体子

Factors()

Factors::Factors ( int n )

inline

前計算

覚え書き

O(n log(log(n)))

factors.hpp の 9 行目に定義があります。

関数詳解

get_prime_factors()

vector< pair< int, int > > Factors::get_prime_factors ( int n )

inline

n を素因数分解する

覚え書き

O(log(n))

factors.hpp の 27 行目に定義があります。

get_divisors()

vector< int > Factors::get_divisors ( int n )

inline

n の約数を返す

覚え書き

O(d(n))

factors.hpp の 45 行目に定義があります。

---

この構造体詳解は次のファイルから抽出されました:

• math/factors.hpp