inamori https://blog.hatena.ne.jp/inamori/ inamori’s diary https://inamori.hateblo.jp/ 数学 Python プロジェクトオイラー http://projecteuler.net/ Q245. (n - φ(n)) / (n - 1)を約分して分子が1になる、合成数の1 < n ≤ 2×1011の総和を求めよ。 最難問題だそうだが、さほどてこずらなかった。 まず、nを素因数分解してべき乗の項があるとダメなのはすぐにわかる。また、偶数もダメ。nが2つの素数の積であるとき、 n = p1p2 (p1 + p2 - 1) / (p1p2 - 1) = 1 / m (p1 - m)(p2 - m) = m2 - m + 1 m2 - m + 1の素因数分解は、n2 + 1のときと同じふるい的な手法がそのまま使… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finamori.hateblo.jp%2Fentry%2F20090805%2Fp1" title="Project Euler 245 - inamori’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2009-08-05 00:00:00 rich https://inamori.hateblo.jp/entry/20090805/p1 1.0 100%