spoj素数猜想PRIMEZUK

Question

我正在试着解决这个问题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);
    }
}

我得到了样本测试用例的正确答案，但当我提交时，我得到了错误的answer...any提示？

Answer 1

你得到了错误的答案，因为"return a/i“也可能返回一个非质数的number.So，你应该检查"return a/i”是否是质数。

试试这个。

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