Вычисление количества простых множителей

На codeforce возникла следующая проблема
Два солдата играют в игру. Вначале первый из них выбирает натуральное число n и передает его второму солдату. Затем второй пытается сделать максимально возможное количество раундов. Каждый раунд состоит из выбора положительного целого числа x > 1, такого, что n делится на x, и замены n на n / x. Когда n становится равным 1 и больше нет возможных допустимых ходов, игра заканчивается, и счет второго солдата равен количеству сделанных им раундов.

Чтобы сделать игру более интересной, сначала солдат выбирает n формы a! / б! для некоторых положительных целых чисел a и b (a ≥ b). Вот к! мы обозначаем факториал 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);  
    }
  } 
}

java algorithm prime-factoring
person Aditya Sharma    schedule 23.05.2015    source источник

Ответы (3)


arrow_upward
2
arrow_downward

В вашем случае а! / б! является

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
person M Oehm    schedule 23.05.2015

arrow_upward
1
arrow_downward

Поскольку ввод для a и b невелик, мы можем создать массив numOfPrime, который по индексу ith,

numOfPrime[i] = number of prime factor of i

Итак, мы замечаем, что numOfPrime[i] = 1 + numOfPrime[i/x] с x является любым простым делителем i.

Для простоты пусть x будет наименьшим простым делителем i, мы можем использовать решето Эратосфена для предварительного расчета x за каждые i

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

Вы можете ознакомиться с моей заявкой по этой задаче.

person Pham Trung    schedule 23.05.2015

arrow_upward
0
arrow_downward

На основе ответа @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++;
}
person Eric Leibenguth    schedule 23.05.2015