C++で素因数の累乗のGCDが1に等しい範囲の数を数えます

正の整数の範囲を表す2つの数値の開始と終了が与えられます。目標は、範囲[start、end]にあり、その数のすべての素因数がGCDを1として持つような素因数分解を持つすべての数の数を見つけることです。

数の素因数分解が2 ^p の場合 * 3 ^q * 5 ^r …..次に、累乗p、q、r...はgcd=1である必要があります。

例を挙げて理解しましょう。

例

入力- 開始=1、終了=10

出力- 素因数の累乗のGCDが1に等しい範囲内の数の数は次のとおりです。6

説明- 番号は次のとおりです。

2（2 ¹ ）、3（3 ¹ ）、5（5 ¹ ）、7（7 ¹ ）、8（2 ³ ）および10（2 ¹ * 5 ¹ ）。各素因数分解のすべての累乗のgcdは1です。

入力- 開始=11、終了=20

出力- 素因数の累乗のGCDが1に等しい範囲内の数の数は次のとおりです。9

説明- 番号は次のとおりです。

11（11 ¹ ）、12（3 ¹ * 2 ² ）、13（13 ¹ ）、14（2 ¹ * 7 ¹ ）、15（3 ¹ * 5 ¹ ）、17（17 ¹ ）、18（2 ¹ * 3 ² ）、19（19 ¹ ）および20（2 ² * 5 ¹ ）。各素因数分解のすべての累乗のgcdは1です。

以下のプログラムで使用されているアプローチは次のとおりです

このアプローチでは、累乗ではない範囲の最初から最後までのすべての数値をカウントします。累乗数が不完全な場合、上記の条件を満たすことになります。このために、すべての累乗数を見つけて、合計数からそれらを削除します。

答えは=start-end+1-（範囲[start、end]内の累乗数の数）

• 範囲変数の開始と終了を入力として取得します。
• ベクトルvecを使用して、3を超えるパワーを保存します。
• 完全な平方である数を格納するためにセットセットを取ります。
• 完全な平方ではない数を格納するためにsetsett_2を設定します。
• 関数calculate（）は、ベクトルvecにデータを入力し、settとsett_2を設定します。完全な平方、非完全な平方、および累乗である数を分離するには>3。
• i=2からi
• 累乗数i*iを設定に挿入します。
• if sett.find（i）！=sett.end（））がtrueを返す場合、iは完全な正方形であり、settに存在するため、何もしません。
• 現在の数値の累乗が大きくなるまでwhileループを実行します。
• 偶数の累乗は完全な平方であり、settにあるため、奇数の累乗をsett_2に挿入します。
• 最後に、ソートされたsett_2の値をforループを使用してベクトルvecに挿入します。
• 関数GCD_1（long int start、long int end）は範囲を入力として受け取り、素因数のGCDが1に等しい範囲内の数値の数を返します。
• calculate（）を呼び出します。
• 範囲内の完全な平方をper_sq=floor（sqrtl（end））-floor（sqrtl（start-1））として計算します。
• upper_bound（vec.begin（）、vec.end（）、end）--vec.begin（）を使用してvecのstartの上限値を計算します。
• 同様に、bottom =lower_bound（vec.begin（）、vec.end（）、start）-vec.begin（）を使用してvecのendの値を低くします。
• 完全な累乗をper_pow=per_sq +（上-下）として計算します。
• 回答はcount=（end --start + 1）--per_powになります。
• 最後に結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
#define size 1000005
#define large 1e18

vector < long int > vec;
set < long int > sett;
set < long int > sett_2;

void calculate() {
   for (long int i = 2; i < size; i++) {
      sett.insert(i * i);
      if (sett.find(i) != sett.end()) {
         continue;
      }
      long int total = i;
      while (i * i <= large / total) {
         total *= (i * i);
         sett_2.insert(total);
      }
   }
   for (auto it: sett_2) {
      vec.push_back(it);
   }
}

long int GCD_1(long int start, long int end) {
   calculate();

   long int per_sq = floor(sqrtl(end)) - floor(sqrtl(start - 1));
   long int top = upper_bound(vec.begin(), vec.end(), end) - vec.begin();
   long int bottom = lower_bound(vec.begin(), vec.end(), start) - vec.begin();
   long int per_pow = per_sq + (top - bottom);
   long int count = (end - start + 1) - per_pow;
   return count;
}
int main() {
   long int start = 10, end = 40;
   cout << "Count of numbers in a range having GCD of powers of prime factors equal to 1 are: " << GCD_1(start, end);
   return 0;
}

上記のコードを実行すると、次の出力が生成されます-

出力

Count of numbers in a range having GCD of powers of prime factors equal to 1 are: 7