資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告