最多约数问题-题解（Java代码）已通过！

    代码已通过，难度就是如何解决时间超限的问题！可参考以下代码，如果想仔细研究，可参考这篇博客  (博客地址)

参考代码:

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;
            }
        }
    }
}