C++でのk-大まかな数値またはk-ギザギザの数値

このチュートリアルでは、指定された数値が k-roughであるかどうかをチェックするプログラムを作成します。 またはk-jagged 番号かどうか。

最小の素因数が与えられたk以上である数は、k-roughと呼ばれます。 またはk-jagged 番号。

問題を解決するための手順を見てみましょう。

• 番号を初期化しますn およびk 。
• nの因数であるすべての素数を見つけます それらをベクターに保存します。
• ベクトルから最初の要素を取得し、それを kと比較します nかどうかを確認する k-roughです またはk-jagged 番号かどうか。

例

コードを見てみましょう。

#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と比較してください 目的の出力を取得します。上記と同様のアイデアを実装しますが、スペースと時間の複雑さは少なくなります。

チュートリアルに質問がある場合は、コメントセクションにそのことを記載してください。