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