Truy vấn để tìm xem một số có chính xác bốn yếu tố phân biệt hay không trong C ++

Trong bài toán này, chúng ta được cung cấp số lượng truy vấn Q, mỗi truy vấn có số N. Nhiệm vụ của chúng ta là tạo một chương trình giải các truy vấn để tìm xem một số có đúng bốn thừa số phân biệt hay không trong C ++.

Mô tả vấn đề

Để giải quyết mỗi truy vấn, chúng ta cần tìm xem số N có đúng bốn thừa số phân biệt hay không. Nếu nó có chữ in CÓ, nếu không.

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

Đầu vào :Q =3, 4, 6, 15

Đầu ra :KHÔNG CÓ

Giải thích

Đối với truy vấn 1:Các hệ số của 4 là 1, 2, 4

Đối với truy vấn 2:Các hệ số của 6 là 1, 2, 3, 6

Đối với truy vấn 3:Các thừa số của 15 là 1, 3, 5, 15

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

Một giải pháp đơn giản cho vấn đề là tìm tất cả các yếu tố của số. Điều này được thực hiện bằng cách tìm tất cả các số từ một đến √N và tăng bộ đếm lên 2. Sau đó, kiểm tra xem bộ đếm có bằng 4 hay không và in CÓ hoặc KHÔNG dựa trên đẳng thức của nó.

Ví dụ

#include <iostream>
#include <math.h>
using namespace std;
   int solveQuery(int N){
   int factors = 0;
   for(int i = 1; i < sqrt(N); i++){
      if(N % i == 0){
         factors += 2;
      }
   }
   if(factors == 4){
      return 1;
   }
   return 0;
}
int main() {
   int Q = 3;
   int query[3] = {4, 6, 15};
   for(int i = 0; i < Q; i++){
      if(solveQuery(query[i]))
         cout<<"The number "<<query[i]<<" has exactly four distinct factors\n";
      else
         cout<<"The number "<<query[i]<<" does not have exactly four
      distinct factors\n";
   }
}

Đầu ra

The number 4 does not have exactly four distinct factors
The number 6 has exactly four distinct factors
The number 15 has exactly four distinct factors

Một cách tiếp cận hiệu quả là sử dụng các khái niệm của lý thuyết số cho các số bốn nhân tố. Vì vậy, nếu một số có bốn yếu tố thì

• Nếu số là một lập phương của một số nguyên tố. Sau đó, nó sẽ có bốn yếu tố khác biệt. Ví dụ, nếu N =(p ^ 3), các thừa số sẽ là 1, p, (p ^ 2), N.

• Nếu số đó là tích của hai số nguyên tố phân biệt. Sau đó, nó cũng sẽ có bốn yếu tố khác biệt. Ví dụ:nếu N =p1 * p2, các thừa số sẽ là 1, p1, p2, N.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int N = 1000;
   bool hasFourFactors[1000];
   void fourDistinctFactors() {
      bool primeNo[N + 1];
      memset(primeNo, true, sizeof(primeNo));
      for (int i = 2; i <= sqrt(N); i++) {
         if (primeNo[i] == true) {
            for (int j = i * 2; j <= N; j += i)
               primeNo[j] = false;
         }
      }
      vector<int> primes;
      for (int i = 2; i <= N; i++)
         if (primeNo[i])
            primes.push_back(i);
            memset(hasFourFactors, false, sizeof(hasFourFactors));
   for (int i = 0; i < primes.size(); ++i) {
      int p1 = primes[i];
      if (1 *(pow(p1, 3)) <= N)
         hasFourFactors[p1*p1*p1] = true;
      for (int j = i + 1; j < primes.size(); ++j) {
         int p2 = primes[j];
         if (1 * p1*p2 > N)
            break;
         hasFourFactors[p1*p2] = true;
      }
   }
}
int main() {
   int Q = 3;
   int query[] = {3, 6, 15};
   fourDistinctFactors();
   for(int i = 0; i < Q; i++){
      if(hasFourFactors[query[i]])
         cout<<"The number "<<query[i]<<" has exactly four distinct
         factors\n";
      else
         cout<<"The number "<<query[i]<<" does not have exactly four distinct factors\n";
   }
   return 0;
}

Đầu ra

The number 3 does not have exactly four distinct factors
The number 6 has exactly four distinct factors
The number 15 has exactly four distinct factors