PRIMES2 - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

Chef’s conjecture is actually false for 127 and 351, but no other counterexamples are known. The conjecture is similar to Goldbach’s weak conjecture, which states that every odd number greater than 7 can be expressed as the sum of three odd primes. Goldbach’s weak conjecture his been conditionally proven, contingent on the Riemann hypothesis.

To solve Chef’s conjecture for small numbers, it suffices to loop through all possible values of P2 and P3, for each value checking if N-P22-P33 is prime. This approach can be optimized by trying large values of P3 first, since it’s easier to find solutions to P1+P22 = N-P33 when the right hand side is small (due to the higher density of primes at lower levels).

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

1 Like
2

i am not getting why i am getting WA.please ca anyone check my code.! thanx a lot :slight_smile:

#include
#include
using namespace std;
int main()
{
long long int i,j,k,l,o,p,m,n,x;
long long int arr1[168],arr2[168],arr3[168];
long long int arr[]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};
for(i=0;i<168;i++)
{
arr1[i]=arr[i];
arr2[i]=arr1[i]*arr1[i];
arr3[i]=arr1[i]*arr1[i]*arr1[i];
}
set myset;
myset.insert(arr,arr+168);
while(1)
{
cin>>n;
if(n==0)
return(0);
else
{
for(j=0;j<168;j++)
{
for(k=0;k<168;k++)
{
if(myset.find(n-arr2[j]-arr3[k])!=myset.end())
break;
}
if(k!=168)
break;
}
if(j==168)
cout<<“0 0 0\n”;
else
cout<<n-arr2[j]-arr3[k]<<" “<<arr1[j]<<” "<<arr1[k]<<endl;
}
}

}

3

@varun

Explain what you’re trying to do here-

  pre< for(i=0;i<168;i++) 
``{ arr1[i]=arr[i]; 
arr2[i]=arr1[i]arr1[i];
 arr3[i]=arr1[i]arr1[i]*arr1[i];
 } >
4

I in fact used a application of sieve.
Ran sieve for 10^6 and stored it in a vector.
then found those primes which were <= sqrt and cbrt of given number by means of a nested loop.
Then checked if(n - p2 x p2-p3 x p3 x p3) is a prime or not.