資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中唯一素因子的最大數量
給定任務是在[1, N]範圍內找到一個數可以具有的唯一素因子的最大數量，其中N是給定的。
讓我們用一個例子來理解我們必須做什麼：
輸入 - N=100
輸出 - 3
解釋 - 讓我們在[1, 100]範圍內取30
30 = 3 * 2 * 5 = 唯一素因子。因此，在[1, 100]範圍內，最多可以找到3個唯一因子。
輸入 - N=300
輸出 - 4
下面程式中使用的方案如下
在MaxPrime()函式中，我們將首先檢查(N < 2)。如果是，則返回零，否則繼續。
然後，我們將使用埃拉託斯特尼篩法找出給定數字N之前的全部素數。
初始化兩個int型別的變數pro=1和max=0，分別儲存乘積和最終答案。
在埃拉託斯特尼篩法中，我們將乘以第一組素數，直到乘積保持小於N，方法是寫入- pro=*p;
檢查(pro > N)。如果是，則返回max並向max加1。
在篩法之外，也返回max。
示例
#include <bits/stdc++.h>
using namespace std;
int MaxPrime(int N){
if (N < 2)
return 0;
// Using Sieve of Eratosthenes
bool Arr[N+1];
memset(Arr, true, sizeof(Arr));
int pro = 1, max = 0;
for (int p=2; p*p<=N; p++){
if (Arr[p] == true){
for (int i=p*2; i<=N; i += p)
Arr[i] = false;
/*Multiply first set of prime numbers while product remains smaller than N*/
pro *= p;
if (pro > N)
return max;
max++;
}
}
return max;
}
//Main function
int main(){
int N = 300;
cout << MaxPrime(N);
return 0;
}輸出
如果我們執行上面的程式碼，我們將得到以下輸出：
4
更新於：2020年8月17日
1K+ 次瀏覽
廣告