C++ 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

时间与空间复杂度

上述代码的时间复杂度为(Nsqrt(N)log(N)*M)，其中N是范围中的最大元素，M是提供的范围总数。

上述代码的空间复杂度为O(1)，因为我们在这里没有使用任何额外的空间。<

方法2

在前面的方法中，我们找到了每个范围的p-smooth元素。在这种方法中，我们将获得范围最大值中的所有元素，然后返回它们。<

示例

#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