Truy vấn đếm số cặp đồng nguyên tố không có thứ tự từ 1 đến N trong C ++

Trong bài toán này, chúng tôi đưa ra các truy vấn Q, mỗi truy vấn chứa một số N. Nhiệm vụ của chúng tôi là tạo một chương trình giải các Truy vấn để đếm số lượng các cặp coprime không có thứ tự từ 1 đến N trong C ++.

Đồng nguyên tố còn được gọi là tương đối nguyên tố hoặc nguyên tố lẫn nhau là cặp số chỉ có một thừa số, tức là 1.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào :Q =2, truy vấn =[5, 6]

Đầu ra :10

Giải thích

Các cặp là:(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4) ), (3, 5), (4, 5)

Phương pháp tiếp cận giải pháp

Giải pháp hứa hẹn nhất cho vấn đề là sử dụng Euler’s TotientFunction phi (N). phi (N) tính tổng số các đồng nguyên tố cho đến giá trị lớn hơn N. Hàm Euler’s totient là,

$$ 𝛷 (𝑁) =𝑁 ∏𝑁 / 𝑁 (1 -), $$

Trong đó p là tất cả các thừa số nguyên tố của N.

Bây giờ, chúng ta sẽ tính toán trước giá trị của số lượng các cặp mã số có thứ tự cho đến N. Và sau đó tìm giá trị của mỗi truy vấn từ mảng được tính toán trước.

Ví dụ

#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;
}

Đầu ra

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