‹ 上一题下一题 ›

j01839. 欧拉函数表未做

1000 ms 256 MB 测试点 10 5级·素数与埃氏筛质数与合数素数筛法素数/合数定义与试除判定O(√n 筛法求素数表、区间筛

文件读写输入j01839.in输出j01839.out

题目描述

输出 $φ (1), φ (2), \dots, φ (n)$ （ $φ$ 为欧拉函数： $1 \sim x$ 中与 $x$ 互质的个数），一行空格分隔。

输入格式

一行 $n$ 。

输出格式

一行 $n$ 个整数。

样例

输入

输出

1 1 2 2 4

数据范围

$1 \leq n \leq 1 0^{6}$

输入

输出

答案