10168 - Summation of Four Primes

[Masud]

What is the problem of my code?
any one help me please?

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();	
	}
}

[Sedefcho]

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
source code and to just say "please help me"

[898989]

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

[kbr_iut]

deleted

[Jan]

Code: Select all

sieve(2,10000000);
...
bool *flag=new bool[d];

Don't use such big dynamic (local) arrays. Just declare the array globally.

[kbr_iut]

deleted

[Jan]

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.

[kbr_iut]

code delted after AC

[Jan]

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.

[kbr_iut]

now AC, code removed.

[tajbir2000]

Code: Select all

REMOVED AFTER AC

[AmitMist]

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

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

Code: Select all

deleted after ac

[newkid]

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

[newkid]

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");

[samin_yasar]

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