「POI2002」「HAOI2007」反素数(反质数)
测试数据来自 system/1172
背景
- Idea: 正式比赛题
- Data: 正式比赛题
- Solution: 正式比赛题
- 题面:正式比赛题+Vijos 用户 - 冰火熔寒(UID:1081)(上传)+oistream(美化)
描述
对于任何正整数 \(x\),其约数的个数记作 \(g(x)\)。例如 \(g(1)=1\)、\(g(6)=4\)。
如果某个满足 \(0<i<x\) 的正整数 \(i\) 满足:\(g(x)>g(i)\),则称 \(x\) 为反质数。例如,整数 \(1,2,4,6\) 等都是反质数。
现在给定一个数 \(N\),你能求出不超过 \(N\) 的最大的反质数么?
格式
输入格式
输入只有一行,一个数 \(N\)。
输出格式
输出也只有一行,为不超过 \(N\) 的最大的反质数。
样例
样例输入1
1000
样例输出1
840
数据规模与约定
每个测试点 \(1s\)。
\(1\leq N\leq 2\times 10^9\)。