## project euler -- problem 69

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.

 n Relatively Prime φ(n) n/φ(n) 2 1 1 2 3 1,2 2 1.5 4 1,3 2 2 5 1,2,3,4 4 1.25 6 1,5 2 3 7 1,2,3,4,5,6 6 1.1666... 8 1,3,5,7 4 2 9 1,2,4,5,7,8 6 1.5 10 1,3,7,9 4 2.5

It can be seen that n=6 produces a maximum n/φ(n) for n ≤ 10.

Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

---
φ(n) is the Euler's totient function.
It states
$\varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right)$
where the product is over the distinct prime numbers dividing n.

So, we can deduce that
$\frac{n}{\varphi(n)} = \prod(\frac{p}{p-1})$
Each $\frac{p}{p-1}$ is larger than one. We can see that $\frac{p}{p-1}$ is larger when p is smaller. and $\frac{n}{\varphi(n)}$ has a higher value when there are more smaller p divided by n.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38  #include #include #include   using namespace std; const int N=1000000;   bool isPrime(int n);   int main() { vector primes; for (int i=2; i <= sqrt(N); i++) { if (isPrime(i)) { primes.push_back(i); } } int n=1; for (int i=0; i< primes.size(); i++) { if (n * primes[i] > N) { cout << "Answers to PE 69: " << n << endl; break; } n *= primes[i]; } return 0; }   bool isPrime(int n) { if (n == 2) return true; if (n % 2 == 0) return false; for (int i=2; i <= sqrt(n); i++) { if ( n % i == 0 ) return false; } return true; }

This code runs very fast...

Answers to PE 69: 510510
user  system elapsed
0.001   0.003   0.004