最多约数问题(Java)

Description

正整数x 的约数是能整除x 的正整数。正整数x的约数个数记为div(x)。例如，1，2，5，10 都是正整数10的约数，且div(10)=4。设a 和b是2 个正整数，a≤b，找出a 和b之间约数个数最多的数x。对于给定的2 个正整数a≤b，计算a 和b之间约数个数最多的数。

Input

输入数据的第1行有2个正整数a和 b，a≤1000000000，b≤1000000000。

Output

若找到的a 和b之间约数个数最多的数是x，将div(x)输出。

Sample Input

1 36

Sample Output

其他测试数据：

1 36

9

1000000 2000000

288

999998999 999999999

1024

1 1000000000

1344

100 1000000000

1344

666 666666666

1200

这一题卡了一阵子了，是在看不懂，琢磨不明白书上的代码了，只能照抄了。。。

正整数x可以分解为质因子之积：

$$ x = p_1^{N_1} * p_2^{N_2} * p_3^{N_3} * ... * p_k^{N_k} $$

所以约数div的公式为：

$$ div(x) = (N_1 + 1)(N_2 + 1)...(N_k + 1) $$

期间还参考了:

https://blog.csdn.net/Will_Lee_Buaa/article/details/8513265?utm_source=blogxgwz7

感觉这个有点问题，测试数据没过
https://blog.csdn.net/Tc_To_Top/article/details/43698997?utm_medium=distribute.pc_relevant.none-task-blog-title-1&spm=1001.2101.3001.4242

这个也没看太明白。。
https://blog.csdn.net/changshu1/article/details/47293659?utm_medium=distribute.pc_relevant.none-task-blog-OPENSEARCH-2.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-OPENSEARCH-2.channel_param

这个注释写的多

我自己写的AC代码:

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner cin = new Scanner(System.in);

        int lift;

        int right;

        lift = cin.nextInt();

        right = cin.nextInt();

        MaxDiv maxDiv = new MaxDiv();

        MaxDiv.primes();

        if (lift == 1 && right == 1) {

            MaxDiv.max_num = 1;

            MaxDiv.numb = 1;

        } else {

            MaxDiv.max_num = 2;

            MaxDiv.numb = 1;

            MaxDiv.search(1, 1, 1, lift, right);

        }

        System.out.println(MaxDiv.max_num);

        /*System.out.println(MaxDiv.numb);*/

    }

}

class MaxDiv {

    public static int max_num;				// 存最多的质因子个数

    public static int numb;					// 存质因子最多的数

    public final static int MAXP = 31622;	// 普通数组最大的大小

    public final static int PCOUNT = 3401;	// 素数数组最大的大小

    public static int prime[] = new int[PCOUNT + 1];	// 素数数组

    // 欧拉筛法求素数表

    public static void primes() {

        int k = 0;

        boolean num[] = new boolean[MAXP + 1];

        for (int i = 2; i <= MAXP; i++) {

            num[i] = true;

        }

        for (int i = 2; i <= MAXP; i++) {

            if (num[i]) {

                prime[++k] = i;

            }

            for (int j = 1; j <= k && prime[j] * i <= MAXP; j++) {

                num[prime[j] * i] = false;

            }

        }

    }

    // 这个函数没明白, 照抄书上的

    public static void search(int from, int tot, int num, int low, int up) {

        if (num >= 1)

            if ((tot > max_num) || ((tot == max_num) && (num < numb))) {

                max_num = tot;

                numb = num;

            }

        if (low == up && low > num)

            search(from, tot * 2, num * low, 1, 1);

        for (int i = from; i <= PCOUNT; i++) {

            if (prime[i] > up)

                return;

            else {

                int j = prime[i];

                int x = low - 1;

                int y = up;

                int n = num, t = tot, m = 1;

                // 应该是循环除质因子

                while (true) {

                    m++;

                    t += tot;

                    x /= j;

                    y /= j;

                    if (x == y)

                        break;

                    n *= j;

                    search(i + 1, t, n, x + 1, y);

                }

                m = 1 << m;

                if (tot < max_num / m)

                    return;

            }

        }

    }

}

巴特西