## 10948 - The primary problem

Moderator: Board moderators

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am

### 10948 - The primary problem.

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

plaese help with some tricky input.

Thanks
Junayeed

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
my output are prety much same...except one

for 999983 it gives me the following output
0+999983

thanks for the help
Junayeed

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
OK..i got AC now..thanks everybody
Junayeed

rafi6047
New poster
Posts: 3
Joined: Tue Oct 10, 2006 5:02 pm

### 10948 - The primary problem

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=prime=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
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

### Re: 10948 pls help

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
New poster
Posts: 3
Joined: Tue Oct 10, 2006 5:02 pm
thnx tan_yui. got AC. thnx very much.

bishop
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm

### soorry

sorry

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am

### 10948(Primary Problem)--TLE

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

Code: Select all

``cut after ac``
Last edited by ishtiaq ahmed on Fri Jul 27, 2007 4:00 pm, edited 1 time in total.
No venture no gain

with best regards
------------------------
ishtiaq ahmed

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

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
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am

### post reply of previous submission of 10948

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.
Last edited by ishtiaq ahmed on Fri Jul 27, 2007 4:01 pm, edited 1 time in total.
No venture no gain

with best regards
------------------------
ishtiaq ahmed

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am

### post reply of previous submission of 10948

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

with best regards
------------------------
ishtiaq ahmed

AbiusX
New poster
Posts: 1
Joined: Sat Aug 18, 2007 8:25 pm
Location: Tehran, iran
Contact:

### :( WA

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=1;
isprime=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
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
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