10168 - Summation of Four Primes

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10168

Post by 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();	
	}
}
Hi I am Masud...

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by 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
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 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
Sleep enough after death, it is the time to work.
Mostafa Saad

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

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

Post by kbr_iut »

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
Location: Dhaka, Bangladesh
Contact:

Re: 10168 - Summation of four primes

Post by 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.
Ami ekhono shopno dekhi...
HomePage

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 10168 - Summation of four primes now CE

Post by kbr_iut »

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
Location: Dhaka, Bangladesh
Contact:

Re: 10168 - Summation of four primes

Post by 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.
Ami ekhono shopno dekhi...
HomePage

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

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

Post by kbr_iut »

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
Location: Dhaka, Bangladesh
Contact:

Re: 10168 - Summation of four primes

Post by 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.
Ami ekhono shopno dekhi...
HomePage

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

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

Post by kbr_iut »

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
Location: bangladesh
Contact:

why runtime error??????

Post by tajbir2000 »

Code: Select all

REMOVED AFTER AC
:D
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

Post by AmitMist »

// 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

Post by newkid »

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

Post by 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");
hmm..

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

Re: 10168 - Summation of Four Primes

Post by 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;
}

Post Reply

Return to “Volume 101 (10100-10199)”