### Re: 10948 - The primary problem

Posted:

**Thu May 08, 2008 1:05 pm**Code: Select all

```
Accepted now. But it takes so much time could any one give me a better formula.
```

The UVa Online Judge board

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

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

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

Posted: **Thu May 08, 2008 1:05 pm**

Code: Select all

```
Accepted now. But it takes so much time could any one give me a better formula.
```

Posted: **Sat Jan 22, 2011 10:54 pm**

Accepted

Posted: **Wed Jan 26, 2011 6:17 pm**

Posted: **Thu Mar 17, 2011 7:38 am**

I just wonder that how those people who got 0.00 for this problem? Even they build prime table before, they two sum problem still need O(N) time by implementing hash. Really curious about this.

Posted: **Sat May 05, 2012 8:27 am**

Code: Select all

```
#include<stdio.h>
#define MAX 1000000
#define MAXH MAX/2
char pr[MAX/16+10];
int a[78599];
void seive()
{
int l=1090,i,j;
for(i=3;i<l;i +=2)
{
if(!(pr[i>>4]&(1<<((i>>1)&0x7))))
{
for(j=i*i/2;j<=MAXH;j +=i)
pr[j>>3] |=(1<<(j&0x7));
}
}
}
void isprime()
{
register int i,p=1;
a[0]=2;
for(i=3;i<=99993;i++)
{
if(!(pr[i>>4]&(1<<((i>>1)&0x7))))
{
a[p]=i;
p++;
}
i++;
}
}
int find ( int target, int first, int last)
{
int mid;
if (first > last)
return -1;
mid = (first + last) / 2;
if (a[mid]==target)
return mid;
if (a[mid]<target)
return find( target, mid+1, last);
return find(target, first, mid-1);
}
int main()
{
int i,j,k,l,n,m;
seive();
isprime();
while(scanf("%d",&n)&&n)
{
printf("%d:\n",n);
if(n%2)
{
m= n-2;
if(find(m, 0, 78498)>=0)
{
printf("2+%d",a[find(m, 0, 78498)]);
}
else
printf("NO WAY!");
}
else
{
for(i=0;i+1;i++)
{
m = n-a[i];
if(find(m, 0, 78498)>=0)
{
printf("%d+%d",a[i],a[find(m, 0, 78498)]);
break;
}
}
}
printf("\n");
}
return 0;
}
```

Posted: **Tue May 08, 2012 12:04 am**

Missing a 9 on line 25.

Posted: **Thu Aug 01, 2013 10:38 pm**

I solved this problem by creating an array and a SET with all primes up to 1 million. I looped thru the array getting the difference between the number N that we are looking for and the prime* (i.e. N - primes**), if we have that difference in the SET we found our sum and print it.*

Posted: **Tue Dec 03, 2013 3:09 am**

If you resubmit you'll get TLE. Read this thread.

Posted: **Thu May 01, 2014 9:07 am**

Thanks for these great test cases.Cho wrote:Nothing tricky, just some boundary cases:

Posted: **Thu May 01, 2014 9:11 am**

alexiago wrote:I solved this problem by creating an array and a SET with all primes up to 1 million. I looped thru the array getting the difference between the number N that we are looking for and the prime(i.e. N - primes), if we have that difference in the SET we found our sum and print it.

This problem's almost identical to 543 - Goldbach's Conjecture. If you're having issues, try that problem first and then give this one a shot.

Posted: **Sun Aug 24, 2014 1:05 am**

i have test for all kind of possible case but still getting WA. need some help with tricky test case

here is my code

#include<stdio.h>

#include<cstdio>

int p=0;

int prm[136]={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};

int prime[1000005];

void primecheck()

{

int f;

for(int i=2;i<=1000005;i++)

{

f=0;

for(int j=0;j<136;j++)

{

if(i%prm[j]==0&&i!=prm[j])

{

f=1;

break;

}

}

if(f==0)

{

prime[p]=i;

p++;

}

}

p=0;

}

int main()

{

int n,a=1,f=0,t,flag=0,u=0,l=0;

primecheck();

while(1)

{

scanf("%d",&n);

if(n==0)

break;

t=n;

a=1;

printf("%d:\n",n);

for(int s=0;s<80000;s++)

{

if(prime[s]>=n)

{

p=s;

break;

}

}

u=p-1;

l=0;

while((u-l)>=0)

{

if(prime[l]+prime==n)

{

printf("%d+%d\n",prime[l],prime);

f=1;

break;

}

if(prime[l]+prime>n)

u--;

if(prime[l]+prime<n)

l++;

}

if(f==0)

printf("NO WAY!\n");

f=0;

}

return 0;

}

here is my code

#include<stdio.h>

#include<cstdio>

int p=0;

int prm[136]={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};

int prime[1000005];

void primecheck()

{

int f;

for(int i=2;i<=1000005;i++)

{

f=0;

for(int j=0;j<136;j++)

{

if(i%prm[j]==0&&i!=prm[j])

{

f=1;

break;

}

}

if(f==0)

{

prime[p]=i;

p++;

}

}

p=0;

}

int main()

{

int n,a=1,f=0,t,flag=0,u=0,l=0;

primecheck();

while(1)

{

scanf("%d",&n);

if(n==0)

break;

t=n;

a=1;

printf("%d:\n",n);

for(int s=0;s<80000;s++)

{

if(prime[s]>=n)

{

p=s;

break;

}

}

u=p-1;

l=0;

while((u-l)>=0)

{

if(prime[l]+prime==n)

{

printf("%d+%d\n",prime[l],prime);

f=1;

break;

}

if(prime[l]+prime>n)

u--;

if(prime[l]+prime<n)

l++;

}

if(f==0)

printf("NO WAY!\n");

f=0;

}

return 0;

}

Posted: **Tue Aug 26, 2014 7:22 pm**

Your prime checking is wrong for numbers greater than 769 * 769. You must add to your **prm** arrary all primes less than 1000 to check primality of numbers less than million.

Input
Acc Output
Your Output
982081 is not a prime. 982081 = 991 * 991.

Use code tags. Don't forget to remove your code after getting accepted.

Input

Code: Select all

```
982084
0
```

Code: Select all

```
982084:
17+982067
```

Code: Select all

```
982084:
3+982081
```

Use code tags. Don't forget to remove your code after getting accepted.

Posted: **Sat Nov 07, 2015 6:15 am**

@Obaida: The trick is generating/detecting prime numbers.Obaida wrote:Code: Select all

`Accepted now. But it takes so much time could any one give me a better formula.`