bzoj#P1053. [HAOI2007]反素数ant
[HAOI2007]反素数ant
题目描述
对于任何正整数 ,其约数的个数记作 。例如 ,。如果某个正整数 满足: 且 ,则称 为反质数。例如,整数 等都是反质数。现在给定一个数 ,请求出不超过 的最大的反质数。
输入格式
第一行一个数 。
输出格式
一行,不超过 的最大的反质数。
1000
840
数据规模与约定
对于 的数据,有 。
对于任何正整数 x,其约数的个数记作 g(x)。例如 g(1)=1,g(6)=4。如果某个正整数 x 满足:g(x)>g(i) 且 0<i<x,则称 x 为反质数。例如,整数 1,2,4,6 等都是反质数。现在给定一个数 n,请求出不超过 n 的最大的反质数。
第一行一个数 n。
一行,不超过 n 的最大的反质数。
1000
840
对于 100% 的数据,有 1≤n≤2×109。