反素数

Problem Description
反素数就是满足对于任意i(0<i<x),都有g(i)<g(x),(g(x)是x的因子个数),则x为一个反素数。现在给你一个整数区间[a,b],请你求出该区间的x使g(x)最大。

Input
第一行输入n,接下来n行测试数据
输入包括a,b, 1<=a<=b<=5000,表示闭区间[a,b].

Output
输出为一个整数,为该区间因子最多的数.如果满足条件有多个,则输出其中最小的数.

Sample Input
3
2 3
1 10
47 359

Sample Output
2
6
240

2个回答

说一下我个人的思路(可能算法并不最优,欢迎讨论):
依次从小到大遍历从a到b区间内每一个数:
A)指向一个将被检验的数i;
B)将其对2到i-1(即自身减1,这里会导致算法不最优,可以考虑到sqrt(i))依次求余,每遇到一个余0的给当前计数器加1(记录因子个数);
C)若当前计数比已经得到的之前的最大情况严格大于(保证在因子相同时优先输出小的),则记录下当前的数i和当前的最大因子个数;
D)当前计数器清零,并指向下一个将被检验的数字;
E)重复BCD步骤,直到所有的数字均被检验过。
F)输出到结束时为止因子个数最大的那个数

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!