由网友(南邮)分享简介：对于于所有邪整数x，其约数的个数忘做g(x)。例如g(一)=一、g(六)=四。要是某个邪整数x餍足：g(x)>g(i) 零中文名反艳数外文名Anti-prime number类型数教分类术语性子从二起头持续的量来历HAOI二零零七性子性子1：1个反艳数的量果子一定是从二起头持续的量数.性子2:一定算法完成• 四零分思绪：...

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

如果某个正整数x满足：g(x)>g(i) 0

中文名

反素数

外文名

Anti-prime number

类型

数学

分类

术语

性质

从2开始连续的质

来源

HAOI2007

性质

性质一：一个反素数的质因子必然是从2开始连续的质数.

性质二:

必然

算法实现

• 40分思路：

• 优化前

考虑直接暴力枚举xx以及xx的因数，时间复杂度约为

。

• 优化后

还是考虑直接暴力枚举xx，但是我们可以通过优化枚举因数的时间复杂度来降低整个程序的时间复杂度，这种方法的时间复杂度约为

。

100100分（满分）思路：

什么是反素数？

反素数就是区间内约数个数最多的那个数。根据题目要求，如果有多个满足，选取最大的一个。

上文的引用部分摘自@stupid_one的博客园，有删改。

很显然题目要求的区间就是

。那么我们怎么求反素数呢？

如果我们设p{}p为指数，k{}k为指数的话，那么如果一个数xx可以被分成如下形式。

。

那么xx的因数个数就是

。

如果设p_ipi严格递增，并且

也算在内，则如果

并且

，那么显然这个数不可能是反素数，因为交换和

会更好。所以

递增时

是递减的，这个数xx才可能是反素数。

所以我们可以据此搜索。

素数表可以筛一波，也可以这样：

因为前12个素数的积

，所以最多用到12个素数，手动打素数表即可。

思路和代码分别来自＠罗恺的博客以及@Goes的博客。

优化前的40 分代码（用时7000ms）：

优化后的40分代码（用时6104ms ）：

100分代码：