Confusion regarding a property of Euler's Totient Function

Правка en1, от Aritra741, 2020-09-04 14:21:47

I was trying to solve this problem. When I failed to come up with a memory efficient solution, I looked at some AC solutions. Interestingly, the solutions used a property that states that the minimum number that has a phi value greater than or equal to a given number, must be the first prime number greater than the given number. For example, For 20, the answer is 23. I am looking for a formal proof of this property.

Теги euler-totient, eular phi

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский Aritra741 2020-09-05 10:12:39 14 Tiny change: 'htOJ-1370) prob' -> 'htOJ-1370)(LightOJ 1370) prob'
en5 Английский Aritra741 2020-09-04 16:17:45 182
en4 Английский Aritra741 2020-09-04 15:16:52 182
en3 Английский Aritra741 2020-09-04 14:26:23 7 Tiny change: 'ing for a formal proof of ' -> 'ing for a proof of '
en2 Английский Aritra741 2020-09-04 14:24:40 3 Tiny change: 'solutions. \nInteres' -> 'solutions.\n \nInteres'
en1 Английский Aritra741 2020-09-04 14:21:47 523 Initial revision (published)