進捗 - 私が歌川です

Project Euler で Level1 を25問解くことができた。めでたい。

Problem 69

10⁶以下の自然数nについて、 $\displaystyle \frac{n}{\phi(n)}$ を最大化するnを出力せよ、という問題。
愚直に $\displaystyle \frac{n}{\phi(n)}$ を計算していくと、めちゃくちゃな時間がかかってしんどい。 $O(n^2)$ ぐらい。

実は

素数pに対して、

$\displaystyle \phi(p^n) = p^n (1-\frac{1}{p})$

なので、

$\displaystyle \frac{\phi(p^n)}{p^n} = \frac{p}{p-1}$

が成り立つ。

また、互いに素な自然数m,nに対して、

$\phi(mn)=\phi(m)\phi(n)$

が成り立つ。

ということは……？

$p_n$ をある自然数の素因数とすると、

$\displaystyle \frac{\phi(p_1^{q_1}p_2^{q_2} \cdots p_n^{q_n})}{p_1^{q_1}p_2^{q_2} \cdots p_n^{q_n}} = \frac{\phi(p_1p_2 \cdots p_n)}{p_1p_2 \cdots p_n}$

つまり、 $\displaystyle \frac{n}{\phi(n)}$ の値は、nの素因数によってのみ決まる。
値の比較なんてする必要なかったんや……。

要するに

10⁶を超えないように素数を小さい方から順に掛けて、10⁶を超える直前でまた素数を小さい方から順に掛ける。
素数判定は試し割りでも十分に間に合った。

実装

github.com

#include <iostream>
using namespace std;

bool isprime(int n){
  if(n <= 1) return false;
  if(n == 2) return true;
  for(int i=2;i*i<=n;i++)
    if(n % i == 0) return false;
  return true;
}

int main(){
  int res = 1;
  for(int i=2;res*i<=1000000;++i)
    if(isprime(i)) res *= i;
  for(int i=2;res*i<=1000000;++i)
    res *= i;
  cout << res << endl;
  return 0;
}