Problem 69：Totient maximum

Problem 69：Totient maximum

题目链接：http://static.projecteuler.net/problem=69

题目大意：求$n$（$n leqslant 1000,000$），使得$frac{n}{varphi (n)}$最大.

若$n=prod_{i=0}^s p_i^{e_i}$是$n$的标准分解式，那么$varphi (n)=nprod_{i=0}^s (1-frac{1}{p_i})$.于是$frac{n}{varphi (n)}=frac{1}{prod_{i=0}^s (1-frac{1}{p_i})}$.

而$p_i$是递增的，故每次贪心取最小的$p_i$可以得到最优解，故$n$为满足$n=prod_{i=0}^t p_i leqslant 1000,000$的最大的$n$.

代码如下：

#include <iostream>
#define N 100005
using namespace std;
bool vis[N];
int p[N],k;
void prime(){
    for(int i=2;i<=100000;++i){
        if(!vis[i])p[k++]=i;
        for(int j=0;j<k&&i*p[j]<=100000;++j){
            vis[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
}
int main(void){
    prime();
    int ans=1;
    for(int i=0;i<k&&ans*p[i]<=1000000;++i)ans*=p[i];
    cout<<ans;
}