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 << " 是 " << k << " rough number" << endl;
   }else {
      cout << n << " 不是 " << k << " rough number" << endl;
   }
   return 0;
}

输出结果

如果运行上述程序，则将得到以下结果。

75 是一个 3 rough number

结论

您可以避免将所有素数存储在向量中。并找到n的第一个素因数，并将其与k进行比较以获得所需的输出。用更少的时间和空间来实现与上述类似的想法。