C++で指定された範囲内のK個の奇数の約数を持つ数を検索します

この問題では、L、R、およびkの3つの整数値が与えられます。私たちの仕事は、与えられた範囲でK個の奇数の約数を持つ数を見つけることです。正確にk個の除数を持つ[L、R]の範囲の数の数を見つけます。

1と数自体を除数として数えます。

問題を理解するために例を見てみましょう

入力

a = 3, b = 10, k = 3

出力

2

説明

Numbers with exactly 3 divisors within the range 3 to 10 are
4 : divisors = 1, 2, 4
9 : divisors = 1, 3, 9

ソリューションアプローチ

この問題の簡単な解決策は、k除数を数えることです。したがって、kが奇数になるには（問題に示されているように）、その数は完全な平方でなければなりません。したがって、完全な平方数についてのみ除数の数をカウントします（これによりコンパイル時間が節約されます）。また、除数の数がkの場合、numbercountに1を加算します。

ソリューションの動作を説明するプログラム

例

#include<bits/stdc++.h>
using namespace std;
bool isPerfectSquare(int n) {
   int s = sqrt(n);
   return (s*s == n);
}
int countDivisors(int n) {
   int divisors = 0;
   for (int i=1; i<=sqrt(n)+1; i++) {
      if (n%i==0) {
         divisors++;
         if (n/i != i)
            divisors ++;
      }
   }
   return divisors;
}
int countNumberKDivisors(int a,int b,int k) {
   int numberCount = 0;
   for (int i=a; i<=b; i++) {
      if (isPerfectSquare(i))
         if (countDivisors(i) == k)
            numberCount++;
   }
   return numberCount;
}
int main() {
   int a = 3, b = 10, k = 3;
   cout<<"The count of numbers with K odd divisors is "<<countNumberKDivisors(a, b, k);
   return 0;
}

出力

The count of numbers with K odd divisors is 2