Code: Select all
Accepted now. But it takes so much time could any one give me a better formula.
Moderator: Board moderators
Code: Select all
Accepted now. But it takes so much time could any one give me a better formula.
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;
}
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.
Code: Select all
982084
0
Code: Select all
982084:
17+982067
Code: Select all
982084:
3+982081
@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.