読者です 読者をやめる 読者になる 読者になる

私が歌川です

@utgwkk が書いている

進捗

技術

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

Problem 69

106以下の自然数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の素因数によってのみ決まる。
値の比較なんてする必要なかったんや……。

要するに

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

実装

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;
}