C++で1からNまでの互いに素なペアの数をカウントするためのクエリ

この問題では、それぞれに数Nが含まれるQクエリが与えられます。私たちのタスクは、C++で1からNまでの互いに素なペアの数をカウントするクエリを解決するプログラムを作成することです。

互いに素 互いに素または互いに素とも呼ばれるのは、1つの因子、つまり1のみを持つ数のペアです。

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

入力 ：Q =2、クエリ=[5、6]

出力 ：10

説明

ペアは：（1、1）、（1、2）、（1、3）、（1、4）、（1、5）、（2、3）、（2、5）、（3、4 ）、（3、5）、（4、5）

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

この問題に対する最も有望な解決策は、オイラーのTotientFunction phi（N）を使用することです。 phi（N）は、与えられた値Nまでのコプライムの総数を計算します。オイラーのトーティエント関数は次のとおりです。

$$𝛷（𝑁）=𝑁∏𝑁 / 𝑁（1 −）、$$

ここで、pはすべてNの素因数です。

ここで、Nまでの互いに素のペアの数のカウントの値を事前に計算します。次に、事前に計算された配列から各クエリの値を見つけます。

例

#include <iostream>
using namespace std;
#define N 10001
int phi[N];
int CoPrimePairs[N];
   void computePhi(){
      for (int i = 1; i < N; i++)
         phi[i] = i;
      for (int p = 2; p < N; p++) {
      if (phi[p] == p) {
         phi[p] = p - 1;
         for (int i = 2 * p; i < N; i += p) {
            phi[i] = (phi[i] / p) * (p - 1);
         }
      }
   }
}
void findCoPrimes() {
   computePhi();
   for (int i = 1; i < N; i++)
      CoPrimePairs[i] = CoPrimePairs[i - 1] + phi[i];
}
int main() {
   findCoPrimes();
   int Q = 3;
   int query[] = { 5, 7, 9};
   for (int i = 0; i < Q; i++)
      cout<<"For Query "<<(i+1)<<": Number of prime pairs is "<<CoPrimePairs[query[i]]<<endl;
   return 0;
}

出力

For Query 1: Number of prime pairs is 10
For Query 2: Number of prime pairs is 18
For Query 3: Number of prime pairs is 28