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 » Sat May 06, 2006 2:37 am


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

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

Post by Sedefcho » Wed Jun 21, 2006 2:23 pm

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 » Mon Aug 07, 2006 10:32 pm

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

User avatar
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 » Fri Apr 11, 2008 3:25 am

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 » Fri Apr 11, 2008 4:25 pm

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

User avatar
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 » Fri Apr 11, 2008 10:33 pm

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 » Fri Apr 11, 2008 11:39 pm

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

User avatar
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 » Sat Apr 12, 2008 11:12 am

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 » Sun Apr 13, 2008 12:13 am

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

User avatar
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 » Sun Apr 13, 2008 1:20 am

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 » Sun Jan 11, 2009 8:44 pm

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 » Wed Feb 18, 2009 10:32 pm

// 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 » Wed Feb 18, 2009 10:42 pm

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 » Wed Feb 18, 2009 11:00 pm

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 » Fri Apr 03, 2009 9:04 pm

#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)”