C++의 k-거친 숫자 또는 k-재그 숫자

이 튜토리얼에서는 주어진 숫자가 k-rough인지 확인하는 프로그램을 작성할 것입니다. 또는 k-jagged 숫자인지 아닌지.

가장 작은 소인수가 주어진 k보다 크거나 같은 수를 k-rough라고 합니다. 또는 k-jagged 번호.

문제를 해결하는 단계를 살펴보겠습니다.

• 숫자 초기화 n 및 k .
• n의 약수인 모든 소수 찾기 벡터에 저장합니다.
• 벡터에서 첫 번째 요소를 가져와 k와 비교 n 여부를 확인하기 위해 k-거친 또는 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와 비교 원하는 출력을 얻으려면. 위의 아이디어와 유사한 아이디어를 공간과 시간 복잡성이 더 적은 방식으로 구현합니다.

튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.