Coding is the closest thing we have to superpower ！
描述
欧拉函数（Euler's totient function），即 \varphi (n)，表示的是小于等于 n 的和 n 互质的数的个数，比如说\varphi (1)=1。
当 n 是质数的时候，显然有\varphi (n)=n-1。
给定一个正整数n，求出1~n的所有欧拉函数值。
输入
一个正整数n，n≤5000000。
输出
1~n的所有欧拉函数值，用空格隔开。
样例
输入
100
输出
1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8 12 10 22 8 20 12 18 12 28 8 30 16 20 16 24 12 36 18 24 16 40 12 42 20 24 22 46 16 42 20 32 24 52 18 40 24 36 28 58 16 60 30 36 32 48 20 66 32 44 24 70 24 72 36 40 36 60 24 78 32 54 40 82 24 64 42 56 40 88 24 72 44 60 46 72 32 96 42 60 40
标签