給定一個(gè)大于1，不超過(guò)2000000的正整數(shù)n，輸出歐拉函數(shù)，phi(n)的值。
如果你并不了解歐拉函數(shù)，那么請(qǐng)參閱提示。

提示
歐拉函數(shù)phi(n)是數(shù)論中非常重要的一個(gè)函數(shù)，其表示1到n-1之間，與n互質(zhì)的數(shù)的個(gè)數(shù)。顯然的，我們可以通過(guò)定義直接計(jì)算phi(n)。
當(dāng)然，phi(n)還有這么一種計(jì)算方法。
首先我們對(duì)n進(jìn)行質(zhì)因數(shù)分解，不妨設(shè)n=p1^a1  *  p2^a2  *  ...  *  pk^ak  （這里a^b表示a的b次冪，p1到pk為k個(gè)互不相同的質(zhì)數(shù)，a1到ak均為正整數(shù)），那么
phi(n)=n(1-(1/p1))(1-(1/p2))....(1-(1/pk))
稍稍化簡(jiǎn)一下就是
phi(n)=n(p1-1)(p2-1)...(pk-1)/(p1*p2*...*pk)

計(jì)算的時(shí)候小心中間計(jì)算結(jié)果超過(guò)int類型上界，可通過(guò)調(diào)整公式各項(xiàng)的計(jì)算順序避免(比如先做除法)!

在給定的輸入文件中進(jìn)行讀入： 
一行一個(gè)正整數(shù)n。 不超過(guò)2000000的正整數(shù)n

將輸出信息輸出到指定的文件中: 
一行一個(gè)整數(shù)表示phi(n)。 

零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情

藍(lán)橋杯 數(shù)論