计算素数的数量

Question

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

为了让游戏更有趣，第一个小兵选择n个形式a！ / 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

在你的情况下，一个！ /乙！是

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

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

您必须使用 BigInteger 或者您必须改变您的方法：而不是除 a 的结果！ /乙！分解成质因子，将对阶乘有贡献的因子进行划分，然后合并质因子集合。

用你的例子来说明：

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

Answer 2

由于 a 和 b 的输入很小，我们可以创建一个数组 numOfPrime，在索引 i 处，

numOfPrime[i] = number of prime factor of i

所以，我们注意到 numOfPrime[i] = 1 + numOfPrime[i/x] 和 x 是 i 的任何质因数。

为简单起见，令x为i的最小质因数，我们可以用Sieve of Eratosthenes为每个i[=预计算x 23=]

int[]x = new int[5000001];
for(int i = 2; i < x.length; i++)
    if(x[i] == 0)
       for(int j = i + i; j < x.length; j+= i)
           if(x[j] == 0)
              x[j] = i;

int[]numOfPrime = new int[5000001];

for(int i = 2; i < x.length; i++)
    if(x[i] == 0)
       numOfPrime[i] = 1;
    else
       numOfPrime[i] = 1 + numOfPrime[i/x[i]];

这个问题你可以看看我的submission

Answer 3

基于@m-oehm 的回答：

int[] factors = new int[a-b];
for(int i=0;i<a-b;i++)
   factors[i] = b+1+i;

boolean done = false;
int i = 2;
while(!done){
   done = true;
   for(int j=0; j<a-b; j++){
      if(i>Math.sqrt(factors[j]) && factors[j]!=1){  // factors[j] is prime
         factors[j] = 1;
         count++;
      }else{
         while(factors[j]%i==0){   // divide factors[j] by i as many times as you can
            factors[j]/=i;
            count++;
         }
      }
      if(factors[j]!=1)            // if all factors have reach 1, you're done
         done = false;
   }
   i++;
}

计算素数的数量

Calculating the number of prime factors

java

algorithm

prime-factoring