The hardest gcd problem-??

general
, ,
1

I recently attempted the question the hardest gcd problem. I made a programme which first calculates the gcd of the entire array. then it factorises this gcd and checks whether all its factors are less than or equal to the given number key. if any factor or (the gcd when it happens to be prime) is greater than the number K, it prints ‘NO’. The following is he code for it. Pl help to tell me where the errors are:-

#include <iostream>
#include<cmath>

using namespace std;



int g(int a, int b)
{
    if(a==0)
    {
        return b;
    }
    return g(b%a,a);
}

int gcdall(int * arr,int n)
{
    int result;
    result=arr[0];
    for(int i=1;i<n;i++)
    {
        result=g(result,arr[i]);
    }
    return result;
}

void print(int key, int k)
{
    int flag=0,prime=1;
    for(int i=2;i<=(key/2);i++)
    {
        if(key%i==0)
        {
            prime=0;
            if(i>k)
            {
                flag=1;
                break;
            }
        }
    }
    if(prime==1 && key>k)
    {
        flag=1;
    }
    if(flag==1)
    {
        cout<<"NO\n";
    }
    else
    {
        cout<<"YES\n";
    }
}

int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        int n,k;
        cin>>n>>k;
        int * arr;
        arr=new int[n];
        for(int i=0;i<n;i++)
        {
            cin>>arr[i];
        }
        int key=gcdall(arr,n);
        print(key,k);
    }
}
2

Your logic is incorrect whether all its factors are less than or equal to the given number key.
E.g. - G= 2^10 and K=300. Your answer is NO . But correct answer is YES. Because we can divide each no by 2 (10 times) to meet requirement.

And you will also need a better method to check primes. Do search for efficient method to check a number is prime or not.

P.S. - Next time do add question link and your soln link. It helps while helping. You added your logic. It helped me in debuging easily.

3

thanks. got the point. i have just started college. learning slowly