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