10948 - The primary problem

[Junayeed]

I think this problem is prety easy, but i am getting WA.

plaese help with some tricky input.

Thanks

[Cho]

Nothing tricky, just some boundary cases:

Code: Select all

4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
999980
999981
999982
999983
999984
999985
999986
999987
999988
999989
999990
999991
999992
999993
999994
999995
999996
999997
999998
999999
1000000
0

Output:

Code: Select all

4:
2+2
5:
2+3
6:
3+3
7:
2+5
8:
3+5
9:
2+7
10:
3+7
11:
NO WAY!
12:
5+7
13:
2+11
14:
3+11
15:
2+13
16:
3+13
17:
NO WAY!
18:
5+13
19:
2+17
20:
3+17
999980:
19+999961
999981:
2+999979
999982:
3+999979
999983:
NO WAY!
999984:
5+999979
999985:
2+999983
999986:
3+999983
999987:
NO WAY!
999988:
5+999983
999989:
NO WAY!
999990:
7+999983
999991:
NO WAY!
999992:
13+999979
999993:
NO WAY!
999994:
11+999983
999995:
NO WAY!
999996:
13+999983
999997:
NO WAY!
999998:
19+999979
999999:
NO WAY!
1000000:
17+999983

[Junayeed]

my output are prety much same...except one

for 999983 it gives me the following output
0+999983

thanks for the help

[Junayeed]

OK..i got AC now..thanks everybody

[rafi6047]

someone pls help me out. im getting wa with this code, i've tried so many test cases, all the outputs r right. but still gettin wa. pls help.




#include<iostream.h>
#include<math.h>


#define P 1000002


bool prime[P];


int main()
{
int i,j;

prime[0]=prime[1]=1;

for(i=2; i<=sqrt(P-1); i++)
{
if(prime==0)
{
for(j=i*i; j<=P-1; j=j+i)
{
prime[j]=1;
}
}
}


while(cin>>i)
{

if(i==0) break;


for(j=2;j<=i/2;j++)
{
if( (prime[j]==0) && (prime[i-j]==0) ) break;

}

if(j>(i/2)) cout<<"NO WAY!\n";

else
{
cout<<i<<":\n"<<j<<"+"<<(i-j)<<"\n";
}

}
return 0;
}

[tan_Yui]

Hi,
your code didn't return N itself as a part of output, if N cannot be represented as the sum of two prime number.
Please check your output format carefully.

Best regards.

[rafi6047]

thnx tan_yui. got AC. thnx very much.

[bishop]

sorry

[ishtiaq ahmed]

Can anybody help me? I am facing TLE (10.035s). Here is my code

Code: Select all

cut after ac

Please try to help me.

[rio]

Code: Select all

      if(!flag)
      {
         for(i=temp;i>=(number/2);i-=2)
         {
            if(!data[i])
            {
               for(j=3;i+j<=number;j+=2)     <--- ??? why do you need this loop ? 
               {
                  if(!data[j] && i+j==number)
                  {
                     flag=1;
                     printf("%ld:\n",number);
                     printf("%ld+%ld\n",j,i);
                     break;
                  }       

----
Rio

[ishtiaq ahmed]

Thanks rio for replying me.
At first i have generated the prime number upto 1000000. When the input is 18 output will

Code: Select all

18 = 5 + 13;

Firstly i have checked any given number that is greater than 4 even or not. if it is even subtracted it with 1, otherwise 2.

so the number is now 17(temporarily).

then i checked if 2+17==18? if not then enter The first for loop. first for loop handled data from 17 to ...............->(18/2);and as well as the second one that is asked by rio handled data from 3 to(18/2).
Now let see..

Code: Select all

3+17 == 18 (no) (3+17=20 exceeds 18) then
skip checking 3+15== 18. Because 15 is not prime. then
3+13 == 18 (no) (3+13=16< 18)so
5+13 == 18. Then stop and print the result.

So these for two for loops are incremented or decremented by 2.

I think you understand my algorithm. If there any efficient algorithm let me know and also try to find my errors in this code.

[rio]

Yes, I could understand your algorithm, and it is efficient enough.
Few things to say.

1. Actually, you don't need the loop which I mentioned.

Code: Select all

               for(j=3;i+j<=number;j+=2)
               {
                  if(!data[j] && i+j==number)
                  {
                     flag=1;
                     printf("%ld:\n",number);
                     printf("%ld+%ld\n",j,i);
                     break;
                  }      
               }

Look careful. if-block is executed at most once, when j = number - i is a prime.
This waste loop is causing TLE.

2. Its not "NO WAY", but "NO WAY!"

3. 1 is not a prime.

Hope this helps.
----
Rio

[ishtiaq ahmed]

A lot of thanks to rio. Now i get ac. Hope you will help me in future.

[AbiusX]

the same code i used for 543 (Goldbach) dunno watz wrong getting a WA

Code: Select all

#include<iostream>
using namespace std;

#define RANGE 1000010
#define sqrtRANGE 1010
int isprime[RANGE];
int prime[RANGE/10];
int primecount;

inline void primesieve()
{
       unsigned int i,j;
       for (i=0;i<RANGE;++i)
           isprime[i]=i&1;
       isprime[2]=1;
       isprime[1]=0;
       
       for (i=3;i<=sqrtRANGE;i+=2)
           if (isprime[i])
           for (j=i*i;j<RANGE;j+=i*2)
               isprime[j]=0;

               primecount=0;
       for (i=0;i<RANGE;++i)
           if (isprime[i]) 
           {
                           isprime[i]=primecount;
                           prime[primecount++]=i;
           }
//           cout <<primecount<<endl;
}


int main()
{
    primesieve();
    int n,i,j,a,b;
    while(cin>>n,n)
    {
                   a=0;
                   b=n-1;
                   while (!isprime[b]) b--;
                   b=isprime[b];
                   while (prime[b]+prime[a]!=n && a<=b)
                   {
                         while (prime[b]+prime[a]>n) 
                         {
                               b--;
                         }
                         while (prime[b]+prime[a]<n)
                         {
                                a++;
                         }
                                
                         if (prime[b]+prime[a]!=n) a++;
                   }
                   if (a<=b)
                      cout <<n<<":"<<endl<<prime[a]<<"+"<<prime[b]<<endl;
                   else
                   {
//                       cout <<n<<endl;
                       cout<<n<<":"<<endl<<"NO WAY!"<<endl; //never happens!
                   }
    }                     
    return 0;
}

tQ

[sapnil]

Try this case:

Code: Select all

Input:
1000000
999999
99999
1
2
3
11
121
100
Output:
1000000:
17+999983
999999:
NO WAY!
99999:
NO WAY!
1:
NO WAY!
2:
NO WAY!
3:
NO WAY!
11:
NO WAY!
121:
NO WAY!
100:
3+97

Thanks
Keep posting
Sapnil