спой премьер гипотеза ПРИМЕЗУК
Я пытаюсь решить вопрос 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);
}
}
я получаю правильный ответ для примера теста, но когда я отправляю, я получаю неправильный ответ … какие-либо подсказки ???
Решение
Вы получаете неправильный ответ, потому что «return a / i» также может возвращать не простое число. Так что вы должны проверить, является ли «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;
}
Другие решения
Других решений пока нет …