数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究P-光滑数在给定范围内
P-光滑数是指其最大质因数小于或等于给定数 P 的数字。质数是指只能被 1 和自身整除的数字。默认情况下，对于任何给定的 P 值，1 都被视为 P-光滑数。在本问题中，我们将得到一个 P 值和一个范围，我们必须返回该范围内存在且为 P-光滑的元素数量。
输入
Given the value of P is 7 and the range is 10 to 20 (where 10 and 20 are inclusive) and 1 to 10;
输出
10, 12, 14, 15, 16, 18, 20. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
解释
在给定的范围内，数字 11、13、17 和 19 是质数，其最大质因数等于自身，并且大于给定 P 值。
对于其余元素，最大因数小于或等于 7。
对于第二个范围，我们所有元素的最大质因数都小于或等于 p 或 7。
方法 1
在这种方法中，我们将遍历给定的范围，并对每个元素，我们将找到每个数字的最大质因数，如果该值小于或等于给定数字，那么我们将返回它们。
示例
#include <bits/stdc++.h>
using namespace std;
// function to find the max prime integer
int maxPrimeDivisor(int cur){
int res = 1;
// base condition
if (cur == 1) {
return res;
}
while (cur % 2 == 0) {
res = 2;
cur = cur / 2;
}
// getting the sqrt root
int squareRoot = sqrt(cur) + 1;
for (int i = 3; i < squareRoot; i += 2) {
while (cur % i == 0) {
res = i;
cur /= i;
}
}
// When cur is prime itself
res = max(res, cur);
return res;
}
// function to find the P smooth in the given range
void findPSmooth(int l, int r, int p){
// traversing over the given range of elements
for(int i =l ; i<= r; i++){
int cur = maxPrimeDivisor(i);
if(cur > p){
continue;
}
else{
cout<<i <<" ";
}
}
cout<<endl;
}
int main(){
int p = 7; // defining the variables
int n = 2; // total number of ranges
// array to define the ranges
int arr[][2] = {{10, 20}, {1, 10}};
// calling the function to find the result
for(int i=0; i<n;i++){
cout<<"The elements which are P-Smooth in the range of "<<arr[i][0]<<" and "<<arr[i][1]<<" are: "<<endl;
findPSmooth(arr[i][0], arr[i][1], p);
}
return 0;
}
输出
The elements which are P-Smooth in the range of 10 and 20 are: 10 12 14 15 16 18 20 The elements which are P-Smooth in the range of 1 and 10 are: 1 2 3 4 5 6 7 8 9 10
时间和空间复杂度
上述代码的时间复杂度为 (N*sqrt(N)*log(N)*M)，其中 N 是范围中的最大元素，M 是提供的范围总数。
上述代码的空间复杂度为 O(1)，因为我们在这里没有使用任何额外的空间。
方法 2
在之前的方法中，我们为每个范围找到了 p-光滑元素。在这种方法中，我们将获取范围最大值中的所有元素，然后返回它们。
示例
#include <bits/stdc++.h>
using namespace std;
vector<int> p_smooth;
// function to find the max prime integer
int maxPrimeDivisor(int cur){
int res = 1;
// base condition
if (cur == 1) {
return res;
}
while (cur % 2 == 0) {
res = 2;
cur = cur / 2;
}
// getting the sqrt root
int squareRoot = sqrt(cur) + 1;
for (int i = 3; i < squareRoot; i += 2) {
while (cur % i == 0) {
res = i;
cur /= i;
}
}
// When cur is prime itself
res = max(res, cur);
return res;
}
// function to get the p_smooth elements
void calPSmooth(int mx, int p){
for(int i=1; i<=mx; i++){
if(maxPrimeDivisor(i) <= p){
p_smooth.push_back(i);
}
}
}
// function to find the P smooth in the given range
void findPSmooth(int l, int r){
// traversing over the given range elements
for(int i = 0 ; i< p_smooth.size(); i++){
if(p_smooth[i] > r){
break;
}
if(p_smooth[i] >= l){
cout<<p_smooth[i]<<" ";
}
}
cout<<endl;
}
int main(){
int p = 7; // defining the variables
int n = 2; // total number of ranges
int mx = 100; // maximum range
// array to define the ranges
int arr[][2] = {{10, 20}, {1, 10}};
// calling the function to get all the pSmooth elements
calPSmooth(mx,p);
// calling the function to find the result
for(int i=0; i<n;i++){
cout<<"Element which are P-Smooth in the range "<<arr[i][0]<<" "<<arr[i][1]<<" are: "<<endl;
findPSmooth(arr[i][0], arr[i][1]);
}
return 0;
}
输出
The elements which are P-Smooth in the range of 10 and 20 are: 10 12 14 15 16 18 20 The elements which are P-Smooth in the range of 1 and 10 are: 1 2 3 4 5 6 7 8 9 10
时间和空间复杂度
上述代码的时间复杂度为 (M*sqrt(M)*log(M) + N)，其中 N 是范围中的最大元素，M 是提供的范围总数。
上述代码的空间复杂度为 O(M)，因为我们正在存储 p-光滑元素。
结论
在本教程中，我们实现了查找给定范围内 P-光滑数的代码。P-光滑数是指其最大质因数小于或等于给定数 P 的数字。我们实现了时间复杂度为 (M*sqrt(M)*log(M) + N) 和 (N*sqrt(N)*log(N)*M) 的代码。此外，空间复杂度为 O(1) 和 O(M)。
更新于: 2023年9月1日
158 次查看
广告