数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 C++ 中查找将 N 减少到 1 的最大操作数
概念
对于给定的两个数字 P 和 Q（P 和 Q 最多可以是 10^6），它们构成一个数字 N = (P!/Q!)。我们的任务是通过执行尽可能多的操作来将 N 减少到 1。请记住，在每次操作中，如果 N 可以被 X 整除，则可以将 N 替换为 N/X。确定可能的最大操作数。
输入
A = 7, B = 4
输出
4
解释
N 是 210，除数是 2、3、5、7
输入
A = 3, B = 1
输出
2
解释
N 是 6，除数是 2、3。
方法
已经观察到，数字 P!/Q! 的因式分解与数字 (Q + 1)*(Q + 2)*…*(P – 1)*P 的因式分解相同。
还应该注意，如果我们仅用其素因子除以 N，则操作数将最大。因此，换句话说，我们需要确定 N 的素因子的计数，包括重复的素因子。
假设计算从 2 到 1000000 的每个数字的因式分解中的素因子的数量。
首先，实现**埃拉托斯特尼筛法**来确定这些数字中每个数字的素数除数。解释如下：
构建一个从 2 到 N 的连续整数列表：（2、3、4、…、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;
}输出
4
更新于：2020-07-25
82 次浏览
广告