### 10948 - The primary problem.

Posted:

**Sat Oct 22, 2005 7:37 am**I think this problem is prety easy, but i am getting WA.

plaese help with some tricky input.

Thanks

plaese help with some tricky input.

Thanks

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=32&t=12354

Page **1** of **2**

Posted: **Sat Oct 22, 2005 7:37 am**

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

plaese help with some tricky input.

Thanks

plaese help with some tricky input.

Thanks

Posted: **Sat Oct 22, 2005 8:00 am**

Nothing tricky, just some boundary cases:
Output:

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
```

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
```

Posted: **Sat Oct 22, 2005 2:27 pm**

my output are prety much same...except one

for 999983 it gives me the following output

0+999983

thanks for the help

for 999983 it gives me the following output

0+999983

thanks for the help

Posted: **Sat Oct 22, 2005 2:59 pm**

OK..i got AC now..thanks everybody

Posted: **Tue Oct 10, 2006 5:08 pm**

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;

}

#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

{

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;

}

Posted: **Tue Oct 10, 2006 7:01 pm**

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.

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.

Posted: **Wed Oct 11, 2006 7:04 am**

thnx tan_yui. got AC. thnx very much.

Posted: **Wed Jul 11, 2007 9:15 pm**

sorry

Posted: **Thu Jul 26, 2007 8:37 pm**

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

Code: Select all

`cut after ac`

Posted: **Fri Jul 27, 2007 2:35 am**

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

Posted: **Fri Jul 27, 2007 7:15 am**

Thanks rio for replying me.

At first i have generated the prime number upto 1000000. When the input is 18 output will
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..
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.

At first i have generated the prime number upto 1000000. When the input is 18 output will

Code: Select all

`18 = 5 + 13;`

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.
```

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

Posted: **Fri Jul 27, 2007 8:07 am**

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.
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

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

This waste loop is causing TLE.

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

3. 1 is not a prime.

Hope this helps.

----

Rio

Posted: **Fri Jul 27, 2007 3:59 pm**

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

Posted: **Sat Aug 18, 2007 8:39 pm**

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

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

Posted: **Tue Oct 09, 2007 8:32 am**

Try this case:

Thanks

Keep posting

Sapnil

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
```

Keep posting

Sapnil