แบบสอบถามเพื่อค้นหาว่าตัวเลขมีตัวประกอบที่แตกต่างกันสี่ตัวหรือไม่ใน C++

ในปัญหานี้ เราได้รับคำถามจำนวน Q โดยแต่ละรายการมีตัวเลข N หน้าที่ของเราคือสร้างโปรแกรมเพื่อแก้ปัญหาการสืบค้นเพื่อค้นหาว่าตัวเลขนั้นมีตัวประกอบที่แตกต่างกันสี่ตัวใน C++ หรือไม่

คำอธิบายปัญหา

ในการแก้ปัญหาแต่ละคำถาม เราต้องค้นหาว่าตัวเลข N มีตัวประกอบที่แตกต่างกันสี่ตัวหรือไม่ หากมีการพิมพ์ YES แสดงว่าไม่มี

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล :Q =3, 4, 6, 15

ผลผลิต :ไม่เป็นไร

คำอธิบาย

สำหรับข้อความค้นหา 1:ตัวประกอบของ 4 คือ 1, 2, 4

สำหรับข้อความค้นหา 2:ตัวประกอบของ 6 คือ 1, 2, 3, 6

สำหรับข้อความค้นหา 3:ตัวประกอบของ 15 คือ 1, 3, 5, 15

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาอย่างง่ายคือการหาตัวประกอบทั้งหมดของตัวเลข ทำได้โดยการค้นหาตัวเลขทั้งหมดจากหนึ่งถึง √N และเพิ่มตัวนับขึ้น 2 จากนั้นตรวจสอบว่าตัวนับเท่ากับ 4 แล้วพิมพ์ YES หรือ NO ตามความเท่าเทียมกัน

ตัวอย่าง

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

ผลลัพธ์

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

วิธีที่มีประสิทธิภาพคือการใช้แนวคิดของทฤษฎีจำนวนสำหรับตัวเลขสี่ตัว ดังนั้น หากตัวเลขมีตัวประกอบสี่ตัวแล้ว

• ถ้าตัวเลขเป็นลูกบาศก์ของจำนวนเฉพาะ จากนั้นจะมีปัจจัยสี่ประการที่แตกต่างกัน ตัวอย่าง ถ้า N =(p^3) ตัวประกอบจะเป็น 1, p, (p^2), N.

• ถ้าตัวเลขเป็นผลคูณของจำนวนเฉพาะสองจำนวนที่แตกต่างกัน จากนั้นจะมีปัจจัยสี่ประการที่แตกต่างกัน ตัวอย่างเช่น ถ้า N =p1*p2 ตัวประกอบจะเป็น 1, p1, p2, N.

ตัวอย่าง

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

ผลลัพธ์

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