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

我得到正確的答案樣本測試案例，但whne我提交我得到錯誤的答案...任何提示???

Answer 1

你得到錯誤的答案，因爲「返回/我」也可能返回你應該檢查是否非黃金number.So「返回/ 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; 
}