Памет: 64MB
Време: 2 сек
В града на числата има N (1<N<100 000 000) жители. На
всеки жител е даден уникален номер (с който участва в различни математически
игри, организирани от
управата на града) .
Уникалният номер е число в интервала [1;N]. Един ден, по случай идването на великия
математик Ойлер в града, управниците организирали следното посрещане. Всичките
N жители били подредени в редица, като на първо място стоял жител, чийто номер
е 1, на второ място бил жител с номер 2,
на трето място, жител с номер 3, т.е. всеки жител заел това място в
редицата, което съответствало на неговия номер. Ойлер минал покрай така
наредената редица от
хора, започвайки от
първия в редицата. Великият математик решил да пробва математическите знания на
жителите на града, като на произволни хора от редицата задал следния въпрос:
“Колко е броят на хората, преди теб в редицата, чийто
номер няма други общи делители с твоя номер освен +1 и
-1?”.
Напишете програма, която отговаря
правилно на въпроса на Ойлер, така както би отговорил N-тия човек в редицата.
Вход:
Входните данни се четат от стандартния вход. На първия и единствен ред e зададено
цялото числото N, броят жители в града .
Изход:
Резултатът-цяло число, да се изведе на стандартния изход. На първия и
единствен ред да се запише отговора на N-тия жител.
8 13
4 12
Хората с номера 1, 3, 5 и
7 Хората с
номера от 1 до 12