求除“1”为公因数外的n个数的公因数

Question

这是我用 gcc 编写的代码。不知道我的逻辑是否不正确，或者我在做其他一些事情 mistake.The 每次输出都为 0。

int main()
{
int n,a[20],count=0;
cin>>n;

for(int i=0;i<n;i++)
{
    cin>>a[i];
}

for(int k=0;k<n;k++)
{
    int c=0;
    for(int j=2;j<n;j++)
    {
        if(a[k]%j==0)
        {
            c++;
        }
        else
        {
            continue;
        }
    }
    if(c==n)
    {
      count++;
    }
}
cout<<count;
}

Answer 1

根据我收集到的信息，您的方法不正确。您应该获取从 2 到 max(a)[1] 的每个数字，并检查它是否是 a 中每个数字的 factor/divisor。如果是，您可以递增 count.

[1] 甚至更好的 max(sqrt(a[i]) for a[i] in a) 伪代码语法。

Answer 2

你的循环顺序错了。您正在检查任何数字是否有 n 个分隔符。

尝试交换循环。然后计数将是除以输入的数字的数量。

你也有错误的上限。您需要尽可能高的分频器。

int max_divider = 2;
for (i = 0; i < n; i++) {
    if (a[i] > max_divider) 
    {
        // Naive approach
        max_divider = a[i];
    }
}
// For each number 2..max_divider
for(int j=2;j <= max_divider;j++)
{
    int c=0;
    for(int k=0;k<n;k++)
    {
        if(a[k]%j==0)
        {
            c++;
        }
        else
        {
            continue;
        }
    }
    if(c==n)
    {
      count++;
    }
}

Answer 3

替换这个循环

for(int j=2; j<n; j++)

和

for(int j=2; (j < a[k]); j++)

请注意，您可以删除 else 部分，它没有任何效果。

求除“1”为公因数外的n个数的公因数

Find the number of common factors for n numbers excluding "1" as common factor

c++

algorithm

number-theory