素猜想

Question

我正在努力解决这个SPOJ问题问题。

 #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 1

您的问题是函数chk，它应该返回给定整数的最大素数因子。不幸的是，它返回的是不一定是最大的素数因子(小于给定的输入)。

例如，chk(75)将返回75/3，它是25 -显然不是素数。

以下是解决此问题的一种方法(递归实现)：

typedef unsigned long long t_ull;

t_ull chk(t_ull a)
{
    t_ull root = (t_ull)sqrt(a);
    for(t_ull i=2; i<=root; i++)
    {
        if(a%i==0)
        {
            return chk(a/i);
        }
    }
    return a;
}

请注意，如果没有找到素因子，则函数将返回输入本身(即素数)。

这允许您撤销对flag的使用，只需打印chk的输出：

cout<<"Case #"<<j<<": "<<chk(prod)<<endl;