bzoj#P1053. [HAOI2007]反素数ant

[HAOI2007]反素数ant

题目描述

对于任何正整数 xx,其约数的个数记作 g(x)\operatorname{g}(x)。例如 g(1)=1\operatorname{g}(1)=1g(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\% 的数据,有 1n2×1091\leq n\leq 2\times 10^9