java - 计算素因数的数量

Question

以下是codeforce上的问题
两个士兵正在玩游戏。一开始，他们中的第一个选择一个正整数 n 并将其交给第二个士兵。然后第二个尝试进行最大可能的回合数。每轮包括选择一个正整数 x > 1，使得 n 可被 x 整除，并将 n 替换为 n / x。当 n 等于 1 并且不再有可能的有效移动时，游戏结束，第二个士兵的分数等于他执行的回合数。

为了让游戏更有趣，第一个士兵选择a形式的n!/ b!对于某个正整数 a 和 b (a ≥ b)。在这里，k!我们表示 k 的阶乘，它被定义为所有不大于 k 的正整数的乘积。

第二个士兵的最高得分是多少？

输入 输入的第一行由单个整数 t (1 ≤ t ≤ 1 000 000) 组成，表示士兵玩的游戏数量。

然后是 t 行，每行包含一对整数 a 和 b (1 ≤ b ≤ a ≤ 5 000 000)，定义游戏的 n 值。

输出 每场比赛输出第二个士兵可以获得的最高分数。

所以我尝试计算 n 的素因数的数量(如 n 的素因数分解)。
以下是我的代码，但测试用例失败
a=5000000 和 b=4999995

import java.util.Scanner;
import java.lang.*;

public class Main {

public static void main (String[] args) throws java.lang.Exception
{
    // your code goes here
    int count=0;

    Scanner input=new Scanner(System.in);

    int testcases=input.nextInt();

    for(int m=1;m<=testcases;m++){
        count=0;
        long a=input.nextLong();
        long b=input.nextLong();
        double n=1;

            for(double i=b+1;i<a+1;i++)
                n=n*i;
        //System.out.println(Math.sqrt(n));

            for(int i=2;i<Math.sqrt(n);i++){

                    if(n%i==0){
                        while(n%i==0){
                            n=n/i;

                            count++;
                        }
                    }   
            }

            if(n!=1) count++;

            System.out.println(count);  
    }
  } 
}

Answer 1

就您而言，a!/b!是

3,124,993,750,004,374,998,750,000,120,000,000

比 2^111 稍大。只有 2^53 以下的数字才能安全地表示为具有 double 值的整数。如果您使用long，您可以将其提高到 2^63，但这仍然不够。

您必须使用BigInteger，或者必须更改您的方法:而不是除以 a! 的结果!/b!划分为素因子，将对阶乘有贡献的因子分开，然后合并素因子集。

用你的例子来说明:

5000000 == 2^6 * 5^7
4999999 == 4999999
4999998 == 2 * 3 * 191 * 4363
4999997 == 43 * 116279
4999996 == 2^2 * 1249999

a! / b! == 2^9 * 3 * 5^7 * 43 * 191 * 4363 * 116279 * 1249999 * 4999999