Chương trình C ++ để kiểm tra xem các số đã cho có phải là số nguyên tố hay không

Giả sử, chúng ta có n số nguyên trong một số mảng. Chúng ta phải tìm hiểu xem các số trong mảng có phải là nguyên tố cùng cặp, trùng khớp hay không cùng chuẩn.

• Hai số nums [i] và nums [j] được cho là cặp số cùng chuẩn nếu gcd (nums [i], nums [j]) =1. Điều này sẽ phù hợp với mọi cặp số trong mảng và i

• Các số được cho là trùng chuẩn nếu gcd (nums [i]) =1.

• Nếu chúng không giống nhau, chúng tôi nói rằng chúng không đúng.

Vì vậy, nếu đầu vào là n =4, nums ={7, 11, 13, 17}, thì đầu ra sẽ là các số là số nguyên tố theo cặp.

Nếu chúng ta kiểm tra mọi cặp số trong mảng, gcd của chúng sẽ luôn là 1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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")

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

The numbers are pairwise coprime