Problem 69: Find the value of n < 1,000,000 for which n/φ(n) is a maximum.

Note the following:

n | φ(n) | n/φ(n) |

2 | 1 | 2 |

… | … | … |

5 | 4 | 1.25 |

6 | 2 | 3 |

7 | 6 | 1.167 |

… | … | … |

30 | 8 | 3.75 |

… | … | … |

210 | 48 | 4.375 |

… | … | … |

2310 | 480 | 4.8125 |

… | … | … |

One can note from this are the divisors that make up n:

ie 2 = 2; 6 = 2×3; 30 = 2x3x5; 210 = 2x3x5x7.. etc

It then becomes trivial to deduce the maximum n/φ(n) where 1<n<10^7

```
```
class runner
{
public static double findTotient(int nO){
int n = nO;
boolean[] result = new boolean[n];
int i=2;
do{
if(n % i == 0){
n /= i;
result[i] = true;
}else{
do{
i++;
}while(i 1);
double calc = nO;
for(int k=0; k b2){ b2 = calc; b1=n;}
//System.out.println(n+" "+calc);
}
}
System.out.println(b1+" "+b2);
System.out.println("time: "+(System.currentTimeMillis() - time));
}
}