#P1463. [POI 2001 ] [HAOI2007] 反素数

    ID: 2261 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>搜索数学20012007河南各省省选POI(波兰)素数判断,质数,筛法

[POI 2001 ] [HAOI2007] 反素数

题目描述

对于任何正整数 xx,其约数的个数记作 g(x)g(x)。例如 g(1)=1g(1)=1g(6)=4g(6)=4

如果某个正整数 xx 满足:0<i<x\forall 0 \lt i \lt x,都有 g(x)>g(i)g(x) \gt g(i),则称 xx反质数。例如,整数 1,2,4,61,2,4,6 等都是反质数。

现在给定一个数 NN,你能求出不超过 NN 的最大的反质数么?

输入格式

一个数 NN

输出格式

不超过 NN 的最大的反质数。

输入数据 1

1000

输出数据 1

840

提示

1N2×1091 \leq N \leq 2 \times 10^9