โปรแกรม C++ เช็คเบอร์ที่ให้มาว่าเป็น coprime หรือเปล่า

สมมติว่าเรามีจำนวนเต็ม n จำนวนในอาร์เรย์จำนวน เราต้องค้นหาว่าตัวเลขในอาร์เรย์เป็นคู่ coprime, setwise coprime หรือไม่ใช่ coprime

• ตัวเลขสองตัว nums[i] และ nums[j] เรียกว่า coprime แบบคู่ ถ้า gcd(nums[i], nums[j]) =1 ค่านี้ควรเก็บไว้สำหรับทุกคู่ของตัวเลขในอาร์เรย์และ i

• ตัวเลขจะเรียกว่า setwise coprime ถ้า gcd(nums[i]) =1

• หากไม่เป็นเช่นนั้น แสดงว่าไม่ใช่คู่กรณี

ดังนั้น หากอินพุตเป็น n =4, nums ={7, 11, 13, 17} ผลลัพธ์จะเป็นตัวเลขที่เป็นคู่ของ coprime

หากเราตรวจสอบทุกคู่ของตัวเลขในอาร์เรย์ gcd ของพวกมันจะเป็น 1 เสมอ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

Define an array fac of size: 100 initialized with 0s.
Define an array checkPrime of size: 100 initialized with 0s.
gcdVal := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
    gcdVal := gcd of (nums[i], gcdVal)
    (increase fac[nums[i]] by 1)
if gcdVal is same as 1, then:
   pw := true
   for initialize k := 2, when k < 100, update (increase k by 1), do:
      if checkPrime[k] is non-zero, then:
         Ignore following part, skip to the next iteration
      c := 0
      for initialize j := k, when j < 100, update j := j + k, do:
         c := c + fac[j]
         checkPrime[j] := true
      pw := pw AND true if c <= 1
   if pw is non-zero, then:
      print("The numbers are pairwise coprime")
   Otherwise
      print("The numbers are setwise coprime")
   Otherwise
      print("The numbers are not coprime")

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;

void solve(int n, int nums[]){
   int fac[100] = {0};
   bool checkPrime[100] = {0};
   int gcdVal = 0;
   for(int i = 0; i < n ; i++) {
      gcdVal = __gcd(nums[i], gcdVal); 
      ++fac[nums[i]];
   }
   if(gcdVal == 1) {
      bool pw = true;
      for(int k = 2; k < 100; ++k) { 
         if(checkPrime[k])
         continue;
         int c = 0;
         for(int j = k; j < 100; j += k) {
            c += fac[j];
            checkPrime[j] = true;
         }
         pw = pw && c <= 1;
      }
      if(pw)
         cout<< "The numbers are pairwise coprime";
      else
         cout<< "The numbers are setwise coprime";
   }
   else
      cout << "The numbers are not coprime";
}
int main() {
   int n = 4, nums[] = {7, 11, 13, 17};
   solve(n, nums);
   return 0;
}

อินพุต

4, {7, 11, 13, 17};

ผลลัพธ์

The numbers are pairwise coprime