/ Vijos / 题库 /

天真的因数分解

天真的因数分解

描述

小岛: 什么叫做因数分解呢?
doc : 就是将给定的正整数n, 分解为若干个素数连乘的形式.
小岛: 那比如说 n=12 呢?
doc : 那么就是 12 = 2 X 2 X 3 呀.
小岛: 呜呜, 好难, 居然素数会重复出现, 如果分解后每一个素数都只出现一次, 我就会.

wish: 这样来说, 小岛可以正确分解的数字不多呀.
doc : 是呀是呀.
wish: 现在问题来了, 对于给定的k, 第 k 个小岛无法正确分解的数字是多少?

格式

输入格式

输入只有一行, 只有一个整数 k.

输出格式

输出只有一行, 只有一个整数, 表示小岛无法正确分解出来的第k个数字.

样例1

样例输入1

10

样例输出1

27

限制

对于30%的数据, k <= 2,000,000
对于100%的数据, 1 <= k <= 10,000,000,000

提示

前 10 个小岛无法正确分解出来的数字依次是: 4 8 9 12 16 18 20 24 25 27

信息

ID
1889
难度
7
分类
(无)
标签
(无)
递交数
959
已通过
170
通过率
18%
被复制
1
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

NOIP模拟赛之被时光掩埋的秘密