Page 2 of 4
10168
Posted: Sat May 06, 2006 2:37 am
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();
}
}
Posted: Wed Jun 21, 2006 2:23 pm
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"
Posted: Mon Aug 07, 2006 10:32 pm
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
10168 -RE pliz n e 1 help......
Posted: Fri Apr 11, 2008 3:25 am
by kbr_iut
deleted
Re: 10168 - Summation of four primes
Posted: Fri Apr 11, 2008 4:25 pm
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.
Re: 10168 - Summation of four primes now CE
Posted: Fri Apr 11, 2008 10:33 pm
by kbr_iut
deleted
Re: 10168 - Summation of four primes
Posted: Fri Apr 11, 2008 11:39 pm
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.
Re: 10168 - replaced count with ount,but now TLE
Posted: Sat Apr 12, 2008 11:12 am
by kbr_iut
code delted after AC
Re: 10168 - Summation of four primes
Posted: Sun Apr 13, 2008 12:13 am
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.
Re: 10168 -sorry via I did a mistake.but still TLE
Posted: Sun Apr 13, 2008 1:20 am
by kbr_iut
now AC, code removed.
why runtime error??????
Posted: Sun Jan 11, 2009 8:44 pm
by tajbir2000
Re: 10168 - Summation of Four Primes
Posted: Wed Feb 18, 2009 10:32 pm
by AmitMist
// Plz help me WHY I am getting the Runtime error???
Here is my code------------
Re: 10168 - Summation of Four Primes
Posted: Wed Feb 18, 2009 10:42 pm
by newkid
change your MAX to 10000000 [as the problem statement indicates]
Re: 10168 - Summation of Four Primes
Posted: Wed Feb 18, 2009 11:00 pm
by newkid
there should be dot at the end of impossible. change the above to following
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
this.. cause there might be negative number as well. problem statement says n <= 10000000. there is no lower limit.
Re: 10168 - Summation of Four Primes
Posted: Fri Apr 03, 2009 9:04 pm
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;
}
