木の直径とは ある頂点0からdfs(bfs)によって一番遠い点を求める。その点の一つをkとするとその点からもう一度dfs(bfs)によって一番遠い点を求める。その点の一つをlとすると、k, lが実際の直径となっている。 実装

エラトステネスの篩とは ある整数nが与えられた時、このn以下の素数を高速に列挙する方法である。計算量としてはO(n log log n)である。素数判定の方法をn回繰り返すとo(n √n)となる。これに対してエラトステネスはすごい速い。 エラトステネスの篩によって…

素因数分解とは nを素因酢分解するアルゴリズムは、1 ~ √nに対してaとするとnをaで割れるときにaで割れるだけ割れば良い。この時aが素数でなければaを分解せねばならないが、aは必ず素数である。 最後に残った数は素因数となっているので追加する。ここで1に…

約数列挙とは nの約数を考える。これは、素数判定と同様に1 ~ √nの間でのみ判定して、割り切れた整数をaとすると、それと同時にn / aを答えに追加すれば良い。 ここで注意点だが、a = n / aの時に両方を追加してはならない。 実装 // また実装する必要がある…

素数判定とは 与えられた整数nが素数かそうでないかを判定するアルゴリズムである。 普通に考えると、2 ~ n-1 でnが割り切れないかを確認すれば良い。しかし、 n = abとすると、min(a, b)は√nを超えない。これより2 ~ √nの間でのみ割り切れないかを考えると…