#P1053. [HAOI2007]反素数ant

    ID: 56 传统题 1000ms 128MiB 尝试: 5465 已通过: 2525 难度: 5 上传者: 标签>CF1800普及+/提高-约数个数乘积公式交换论证深度优先搜索可行性剪枝

[HAOI2007]反素数ant

题目描述

对于任何正整数 xx,其约数的个数记作 g⁡(x)\operatorname{g}(x)。例如 g⁡(1)=1\operatorname{g}(1)=1,g⁡(6)=4\operatorname{g}(6)=4。如果某个正整数 xx 满足:g⁡(x)>g⁡(i)\operatorname{g}(x)>\operatorname{g}(i) 且 0<i<x0<i<x,则称 xx 为反质数。例如,整数 1,2,4,61,2,4,6 等都是反质数。现在给定一个数 nn,请求出不超过 nn 的最大的反质数。

输入格式

第一行一个数 nn。

输出格式

一行,不超过 nn 的最大的反质数。

1000
840

数据规模与约定

对于 100%100\% 的数据,有 1≤n≤2×1091\leq n\leq 2\times 10^9。