C++에서 N을 1로 줄이는 최대 연산 찾기

<시간/>

컨셉

주어진 두 숫자 P와 Q(P와 Q는 최대 10^6일 수 있음)에 대해 N =(P!/Q!)를 형성합니다. 우리의 임무는 가능한 최대 작업 수를 수행하여 N을 1로 줄이는 것입니다. 각 연산에서 N을 X로 나눌 수 있는 경우 N을 N/X로 바꿀 수 있음을 기억하십시오. 가능한 최대 연산 수를 결정하십시오.

입력

A = 7, B = 4

출력

설명

N은 210이고 제수는 2, 3, 5, 7입니다.

입력

A = 3, B = 1

출력

설명

N은 6이고 제수는 2,3입니다.

방법

숫자 P!/Q!의 인수분해가 관찰되었습니다. 이것은 숫자의 인수분해(Q + 1)*(Q + 2)*...*(P – 1)*P와 동일합니다.

또한 N을 소인수로만 나누면 연산 수가 최대가 된다는 점에 유의해야 합니다. 그 결과, 다시 말해 중복도 포함하는 N의 소인수 개수를 결정해야 합니다.

2에서 1000000까지의 모든 수를 인수분해할 때 소인수 개수를 세어 봅시다.

먼저 에라토스테네스의 체를 구현합니다. 이 숫자들 각각의 소수를 결정하기 위해. 그것은 다음과 같이 설명됩니다 -

(2, 3, 4, …, N) 2에서 N까지의 연속적인 정수 목록을 작성합니다.
처음에는 p가 첫 번째 소수인 2와 같다고 가정합니다.
p^2부터 시작하여 p의 증분으로 세고 p^2보다 크거나 같은 각 숫자를 목록에 표시합니다. 따라서 이 숫자는 p(p+1), p(p+2), p(p+3) 등이 될 수 있습니다.
목록에서 표시되지 않은 p보다 큰 첫 번째 숫자를 결정하십시오. 그러한 번호가 없으면 중지하십시오. 그렇지 않으면 p가 이 숫자(다음 소수를 나타냄)와 같다고 가정하고 3단계부터 다시 반복합니다.

에라토스테네스의 체 방법을 구현한 후 다음 공식을 구현하는 인수분해에서 소인수 수를 계산할 수 있습니다. -

Primefactors[num] =primefactors[num / primedivisor[num]] + 1현재, 소인수에 대한 접두사 합 배열을 구현한 다음 간격 [P, Q]에 대한 합에 대해 답할 수 있습니다.

예시

// CPP program to find maximum
// number moves possible
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
// Used to store number of prime
// factors of each number
int primeFactors1[N];
// Shows Function to find number of prime
// factors of each number
void findPrimeFactors(){
   for (int a = 2; a < N; a++)
   // Now if a is a prime number
   if (primeFactors1[a] == 0)
      for (int b = a; b < N; b += a)
         // Now increase value by one from
         // it's preveious multiple
   primeFactors1[b] = primeFactors1[b / a] + 1;
   // Build prefix sum
   // this will be helpful for
   // multiple test cases
   for (int a = 1; a < N; a++)
      primeFactors1[a] += primeFactors1[a - 1];
}
// Driver Code
int main(){
   // Create primeFactors1 array
   findPrimeFactors();
   int P = 7, Q = 4;
   // required answer
   cout << primeFactors1[P] - primeFactors1[Q];
   return 0;
}