## 10168 - Summation of Four Primes

Moderator: Board moderators

Masud
New poster
Posts: 5
Joined: Sat May 06, 2006 1:12 am
Contact:

### 10168

What is the problem of my code?

Code: Select all

``````#include<stdio.h>
#include<math.h>

bool flag[10000001];
long int x,y,n;

void sieve(long int L,long int U)
{
long int i,j,d;

d=U-L+1;

for (i=0;i<d;i++) flag[i]=true;

for (i=(L%2!=0);i<d;i+=2) flag[i]=false;

for (i=3;i<=sqrt(U);i+=2) {
if (i>L && !flag[i-L]) continue;

j=L/i*i;
if (j<L) j+=i;
if (j==i) j+=i;

j-=L;
for (;j<d;j+=i) flag[j]=false;
}

if (L<=1) flag[1-L]=false;
if (L<=2) flag[2-L]=true;

}

void solve_it()
{
if(n%2==1)
{
printf("2 3 ");
n=n-5;
}
else
{
printf("2 2 ");
n=n-4;
}
x=3;
y=n-3;

while(1)
{
if(flag[x-1]&&flag[y-1])
break;
x=x+2;
y=y-2;
}
printf("%ld %ld\n",x,y);
}

void main()
{
sieve(1,10000000);

while(scanf("%ld",&n)==1)
{
if(n<8)printf("Impossible.\n");
else if(n==8)printf("2 2 2 2\n");
else solve_it();
}
}
``````
Hi I am Masud...

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
What error do you get ?
If you are getting TLE then, well...
You should not do a sieve up to 10,000,000 but only
up to SQRT(10,000,000), otherwise I think it is normal
to get a TLE.

By the way, it's a bad idea to directly post

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
Your code do not efficently produce prime numbers
You may use Seive with Bitwise operators to generate them, if you do not know what is this, visit the threads of problem 10311 or go to site
http://www.algorithmst.com and see math -> seive

as for your general code, i think you did not handle case input
9 -> 2 2 2 3

every thing else is similar to my code
Sleep enough after death, it is the time to work.

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### 10168 -RE pliz n e 1 help......

deleted
Last edited by kbr_iut on Wed Sep 10, 2008 11:05 am, edited 1 time in total.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 10168 - Summation of four primes

Code: Select all

``````sieve(2,10000000);
...
bool *flag=new bool[d];
``````
Don't use such big dynamic (local) arrays. Just declare the array globally.
Ami ekhono shopno dekhi...
HomePage

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 10168 - Summation of four primes now CE

deleted
Last edited by kbr_iut on Wed Sep 10, 2008 11:05 am, edited 1 time in total.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 10168 - Summation of four primes

You can see the compiler error report now (check your submissions page). The problem is 'count'. 'iostream' has some build-in methods which use 'count'. So, change 'count' to 'Count' or other variable.
Ami ekhono shopno dekhi...
HomePage

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 10168 - replaced count with ount,but now TLE

code delted after AC
Last edited by kbr_iut on Wed Sep 10, 2008 11:04 am, edited 1 time in total.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 10168 - Summation of four primes

The function 'check' is used to check whether a number is prime or not. Suppose a number 'n' is prime, then what is the value of flag[n]? And can you update 'check' with this? And you can use Goldbach's Conjecture to optimize.
Ami ekhono shopno dekhi...
HomePage

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 10168 -sorry via I did a mistake.but still TLE

now AC, code removed.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

tajbir2000
New poster
Posts: 19
Joined: Fri Sep 05, 2008 6:39 pm
Contact:

### why runtime error??????

Code: Select all

``````REMOVED AFTER AC
``````
Last edited by tajbir2000 on Mon Jan 12, 2009 7:20 pm, edited 1 time in total.

AmitMist
New poster
Posts: 6
Joined: Wed Feb 18, 2009 10:20 pm

### Re: 10168 - Summation of Four Primes

// Plz help me WHY I am getting the Runtime error???

Here is my code------------

Code: Select all

``````
deleted after ac
``````
Last edited by AmitMist on Wed Feb 18, 2009 11:21 pm, edited 1 time in total.

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

### Re: 10168 - Summation of Four Primes

change your MAX to 10000000 [as the problem statement indicates]
hmm..

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

### Re: 10168 - Summation of Four Primes

Code: Select all

``printf("Impossible\n");``
there should be dot at the end of impossible. change the above to following

Code: Select all

``printf("Impossible.\n");``
comment the following

Code: Select all

``````        else if(isprime(n))
{
printf("Impossible\n");
}``````
as a counterexample: 13 => 2 3 3 5

and change this to

Code: Select all

``````        if(n==1)
printf("Impossible\n");
``````
this.. cause there might be negative number as well. problem statement says n <= 10000000. there is no lower limit.

Code: Select all

``````        if(n<8)
printf("Impossible.\n");
``````
hmm..

samin_yasar
New poster
Posts: 5
Joined: Sat Mar 28, 2009 6:15 pm

### Re: 10168 - Summation of Four Primes

#include <stdio.h>
#include <math.h>
int prime(int n)
{
int i = 3 , j=0;

if(n%2==0 && n!=2)return 0;

if(n==2)return 1;

for(;i <= sqrt(n) ; i+=2)
{
if( (n%i)==0 ) return 0;

else j=1;

}

if(j==1)return 1;

}
void print(int n)
{
int i;
for( i=2 ; i <= n/2 ;i++)
{
if(prime(i))
{
if(prime(n-i))
{
printf("%d %d",i,(n-i));
break;
}
}
}

}

int main()
{
int num,num1,num2;

while(scanf("%d",&num)==1)
{
if(num<8)printf("Impossible.\n");

else if(num==8)printf("2 2 2 2\n");

else if(num>8)
{
if(num%2!=0)
{
num1 = num-5;

printf("2 3 ");

print(num1);

printf("\n");
}
else
{
if( (num/2)%2==0)
{
num1 = num/2-2;

num2 = num/2+2;

print(num1);

printf(" ");

print(num2);

printf("\n");

}
else
{
num1 = num/2-5;

num2 = num/2+5;

print(num2);

printf(" ");

print(num1);

printf("\n");
}

}

}

}
return 0;
}