时间戳

首页 > 解决方案 > 如何找到数组中相对质数的对？

c++ - 如何找到数组中相对质数的对？

问题描述

我需要将数字放入一个数组中，并取与间隔末尾等距离的数字

示例：6 个数字，{3, 4, 6, 36, 45, 97} -> 3 和 97, 4 和 45, 6 36；

然后我需要检查它们是否相对质数。

示例：3 和 97 是互质数，因为它们没有公约数，4 和 45 也是如此，但 6 和 36 不是，因为它们有 2、3 和 6。

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int n, nn, nnn, v[1000], cntPairs = 0;

    cout << "How many elements?\n";
    cin >> n;

    for(int i=0; i<n; i++)
        cin >> v[i];
    nn = n/2;
    nnn = ceil(n/2);

    cout << "The pairs are: \n";

    if(n % 2 == 0){
        for(int i=0; i<nn; i++){
            if(v[i] % v[n - i - 1] != 0){
                    cntPairs++;
            cout << v[i] << " " << v[n - i - 1] << "\n";
            }
        }
    }
    if(n % 2 == 1){
        for(int i=0; i<nnn; i++){
            if(v[i] % v[n - i - 1] !=0){
                    cntPairs++;
            cout << v[i] << " " << v[n - i - 1] << "\n";
            }
        }
    }
    cout << endl << "Number of pairs: " << cntPairs;

    return 0;
}

现在，我的程序从我所关心的方面做到了这一点，但是如果我将 6 和 36 放在它们之间，它表示它们之间是素数，但它们不是，我找不到一种方法来实现它，所以它对 36 和 6 进行计算，而不是 6 和 36。

我唯一的假设是我必须在 2 中找到最大的并将较大的放在第一位，但我不知道如何。

标签： c++arrays

解决方案

两个整数互质当且仅当它们的最大公约数为 1。因此，要检查x和是否y互质，请执行std::gcd(x, y) == 1（std::gcd 需要 C++17，GCC 有 __gcd，或者自己实现）。

其他意见：

  1. ceil(n/2)等于n/2。(n+1)/2如果您想四舍五入，请使用。
  2. 您不需要单独考虑n偶数和奇数的情况。这适用于所有情况：
for (int i = 0; i < n/2; i++) {
   if (std::gcd(v[i], v[n-i-1]) == 1) {
       /* ... */
   }
}

推荐阅读