#P1463. [POI2001] [HAOI2007] 反素数

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

[POI2001] [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 的最大的反质数。

1000
840

提示

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