数据结构
网络
关系数据库管理系统 (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+ 次浏览
广告