Spoj prem hypothesis PRIMEZUK

Question

I am trying to resolve the issue http://www.spoj.com/problems/PRIMEZUK/

 #include<iostream>
 #include<cstdio>
#include<math.h>
#define l long long
 using namespace std;
l chk(l a)
{
    for(int i=2;i<=sqrt(a);++i)
    {
        if(a%i==0)
        {
            return a/i;
        }
    }
    return 0;
}
main()
{
//  freopen("in.txt","r",stdin);
    int t,n,a;
    l prod=1,flag;
    //t=inp();
    cin>>t;
    for(int j=1;j<=t;++j)
    {
        cin>>n;
        //n=inp();
        if(n==0)
        prod=-1;
        else
        prod=1;
        while(n--)
        {
            cin>>a;
            //a=inp();
            prod*=a;
        }
        ++prod;
        flag=chk(prod);
        if(!flag)
        printf("Case #%d: %lld\n",j,prod);
        else
        printf("Case #%d: %lld\n",j,flag);
    }
}

I get the correct answer for the sample test case, but I imagine that I get the wrong answer ... any hints ???

Answer 1

You get the wrong answer because "return a / i" can also return an odd number. Therefore, you should check whether "return a / i" is simple or not.

Try it...

#include<bits/stdc++.h>

long long int check(long long int a)//Function to check whether a number is prime or not
{
    long long int i,k;
    k=sqrt(a);
    for(i=2;i<=k;++i)
    {
        if(a%i==0) // if not prime
            return check(a/i); //then find greatest prime
    }
    return a;
}

int main()
{
    int j=1,t;
    long long int n,a,prod,flag;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&n);
        if(n==0)
            prod=-1;
        else 
            prod=1;
        while(n--)
        {
            scanf("%lld",&a);
            prod*=a;
        }
        ++prod;
        printf("Case #%d: %lld\n",j,check(prod));
        j++;
    }
    return 0;
}