資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++ 中的 k-粗糙數或 k-鋸齒數
在本教程中，我們將編寫一個程式來檢查給定的數字是否為k-粗糙數或k-鋸齒數。
最小質因數大於或等於給定 k 的數稱為k-粗糙數或k-鋸齒數。
讓我們看看解決問題的步驟。
- 初始化數字n和k。
- 找到所有作為n的因子的質數，並將它們儲存在向量中。
- 從向量中獲取第一個元素，並將其與k比較，以檢查n是否為k-粗糙數或k-鋸齒數。
示例
讓我們看看程式碼。
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n) {
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
vector<int> getPrimes(int n) {
vector<int> primes;
for (int i = 2; i < n; i++) {
if (n % i == 0 && isPrime(i)) {
primes.push_back(i);
}
}
return primes;
}
bool isRoughNumber(int n, int k) {
vector<int> primes = getPrimes(n);
return primes[0] >= k;
}
int main() {
int n = 75, k = 3;
if (isRoughNumber(n, k)) {
cout << n << " is a " << k << " rough number" << endl;
}else {
cout << n << " is not a " << k << " rough number" << endl;
}
return 0;
}輸出
如果執行以上程式，則會得到以下結果。
75 is a 3 rough number
結論
您可以避免將所有質數儲存在向量中。找到n的第一個質因數，並將其與k比較以獲得所需輸出。實現與上述類似的想法，但具有更低的時空複雜度。
如果您在本教程中有任何疑問，請在評論區提出。
更新於：2021年4月9日
瀏覽量：129
廣告