### PROBLEM LINKS

### DIFFICULTY

SIMPLE

### PREREQUISITES

Primality Testing

### PROBLEM

Given some **N**, find the **i** for which **φ(i)/i** is the largest among all **2≤i≤N**.

**φ(i)** is the **Euler Totient Function**.

### QUICK EXPLANATION

**φ(i)** is equal to the number of positive integers less than **i**, which are **co-prime** to **i**. The largest value of **φ(i)/i** is always achieved at prime values of **i** (primes of course are **co-prime** to all values less than them). Note that for a prime **i**, **φ(i) = i-1**.

Thus, for some **N**, we need to find the largest prime number we can find, which is less than **N**.

**N** can be up to **10 ^{18}**. If we test primality via

**Trial Division**, the minimum number of divisions we do for testing the primality of a single number is about

**10**. Considering we have to consider several numbers and try to pluck the prime one (and do so for several cases) we are forced to find a faster way to test primality.

^{9}Miller Rabin is such a test.

### EXPLANATION

Although a **probabilistic** test, **Miller** **Rabin** has been successfully executed up till large enough numbers to show that performing the test while taking the first **9** prime numbers **{ 2, 3, 5, 7, 11, 13, 17, 19, 23 }** as the bases is sufficient to accurately test for primality of all numbers less than **10 ^{18}**.

If you end up falling in love with **Miller** **Rabin** (the algorithm of course), you will find this link very useful to decide how many of the first few prime numbers to use as bases. It is not necessary to use small primes of course. Random bases can be chosen as well. But you might have to choose more than **9** of them to reduce the probability of a falty answer to a comfortably low level (testing with k random bases reduces the probability of a composite being reported as prime by a factor of 1/4^{k})

There are possibly two hurdles that you may face in implementing Miller Rabin.

**1. Finding a ^{r} mod n, for a large r**

This step must be performed using **repeated squaring**.

**2. Multiplying two large integers mod n**

The product of the two large integers would overflow the **64-bit** integer data type as well. The only way to get around this is to use some arbitrary precision math.

We can assume that the two integers, say **a** and **b**, are less than **n**. One way to perform the multiplication is as follows

1. a_low = a % 10^{9}2. a_high = a / 10^{9}3. 4. b_low = b % 10^{9}5. b_high = b / 10^{9}6. 7. result = (a_high * b_high) % n 8. 9. repeat 9 times 10. result = (result * 10) % n 11. 12. result = (result + a_low*b_high + b_low*a_high) % n 13. 14. repeat 9 times 15. result = (result * 10) % n 16. 17. result = (result + a_low*b_low) % n

The reason the above procedure would work is

- The product in line 7, 12 and 17 are betwee two 30-bit integers and will not overflow 64-bit integers.
- The product in line 10 and 15 are between a 60-bit integer and 4-bit integer and will not overflow 64-bit integers. (although we must use unsigned)

### SETTER’S SOLUTION

Setter’s solution will be updated soon.

### TESTER’S SOLUTION

Can be found here.