## 543 - Goldbach's Conjecture

Moderator: Board moderators

rocky11
New poster
Posts: 1
Joined: Tue Aug 02, 2005 8:31 pm
Contact:

### 543 why WA

/* i used prime_facto function to check the number is prime or not. if the function prime_facto returns 1 thus the number is prime.

what will be the condition for N<6 and N%2!=0 ... is it GOlbach's conjecture false will be printed or only continue;

*/

Code: Select all

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

#define MAX 1000000

long _prime[MAX];

void seive()
{
long limit=MAX, i,j;
_prime[0]=_prime[1]=1;
for(i=4;i<=limit;i+=2) _prime[i]=1;
for(i=3;i<=sqrt(limit);i+=2)
if(_prime[i]==0)
for(j=i*i;j<=limit;j+=i+i)
_prime[j]=1;

}

long prime_facto(long  x)

{

long  i;
long  c,m=0;

c=x;

while((c%2)==0)
{
long x=2;
m++;
//	printf("%ld,",x);
c=c/2;
}

i=3;
while(i<=(sqrt(c)+1))
{

if((c%i)==0)
{
//		printf("%ld,",i);
c=c/i;
m++;

}

else
i=i+2;
}

if(c>1)
m++;
//	printf("%ld,",c);

return m;
}

int main()
{
long len,prime[100000],x,primal,flag,i,j=0,k,N;

long n=1000000;

seive();

k=0;

for(i=0;i<n;i++)
{
if(_prime[i]!=1)
prime[k++]=i;
}

freopen("x.in","r",stdin);

while(scanf("%llu",&N)==1)
{
if(N==0)
break;

if(N<6)
{
flag=0;
goto l2;
}

if((N%2)!=0)
{
flag=0;
goto l2;
}

for(i=k-1;i>=0;)
if(prime[i]>N)
{
i--;
}

else
{
goto l1;
}

l1:
x=N-prime[i];

len=prime_facto(x);

if(x==1 && i>=0)
{
prime[i--];
goto l1;
}

if(len!=1 && i>=0)
{
prime[i--];
goto l1;
}

else
{
flag=1;
primal=prime[i];
}

l2:

if(flag)
printf("%llu = %llu +%llu\n",N,x,primal);
else
printf("Goldbach's conjecture is wrong.\n");

}
return 0;
}``````
[/code]
Kazi Farhan Ahmed (Dhaka City College)
DCC_PIONEER.

esmitt
New poster
Posts: 2
Joined: Thu Aug 18, 2005 7:52 am
Location: Venezuela
Contact:

### 543 WA, i need help

It's my first post.
This problems is WA !!!, but I cannot find the wrong.

Code: Select all

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

#define N 1000001
bool isprime[N];
typedef unsigned int uint;

void fill() //sieve
{
memset(isprime,1,sizeof(bool)*N);

for(uint i = 2; i < N; i++)
{
if(isprime[i])
for(uint k = i*i; k < N; k+=i)
isprime[k] = false;
}
}

void find(uint n)
{
uint i;

for(i = 2; i < n; i++)
{
if(isprime[i] && isprime[n-i])	// i + n - i = n
{
printf("%u = %u + %u\n",n,i,n-i);
return;
}
}

printf("Goldbach's conjecture is wrong.\n");
}

main()
{
fill();
uint n;
while(scanf("%u",&n)!=EOF)
{
if(n == 0)break;
find(n);
}
return 0;
}
``````
Esmitt Ram

esmitt
New poster
Posts: 2
Joined: Thu Aug 18, 2005 7:52 am
Location: Venezuela
Contact:

### Accepted 543

I got AC.
I was wrong my fill ( ) function.

Code: Select all

``````void fill() //sieve
{
memset(isprime,1,sizeof(bool)*N);

for(uint i = 2; i < N; i++)
{
if(isprime[i])
for(uint k = (i<<1); k < N; k+=i)
isprime[k] = false;
}
}
``````
Esmitt Ram

georgemouse
New poster
Posts: 13
Joined: Sun Aug 28, 2005 3:39 pm
Location: Taiwan

### 543

I got tle but I don't know how to make it faster!!
Can someone help me?
thanks!!!!

Here is my code:

Code: Select all

``removed after AC``
Last edited by georgemouse on Tue Jan 31, 2006 4:06 pm, edited 1 time in total.

artem
New poster
Posts: 17
Joined: Thu Jun 09, 2005 5:01 pm
Your prime number generator very slow.
this my code to generate prime numbers:

Code: Select all

``````int mas[100000],in;
char matr[1000001];

int prost(){
int i,j,t;
for (i=3;i<1000001;i+=2)
if (!matr[i]){
mas[in++]=i;
t=i+i;
for (j=i;j<1000001;j+=t)
matr[j]=1;
}
return 0;
}
``````
this function generate all primes 2< < 1000001 (in this problem 2 not needed)

georgemouse
New poster
Posts: 13
Joined: Sun Aug 28, 2005 3:39 pm
Location: Taiwan
To artem:

But I still got TLE...........Why???
Is my method to find the pair of prime too slow?
I tried to modify my method to find the pair, but it seems no use.....

Can anyone tell me what's wrong in my code?

Code: Select all

`` removed after AC``
Last edited by georgemouse on Tue Jan 31, 2006 4:06 pm, edited 1 time in total.

georgemouse
New poster
Posts: 13
Joined: Sun Aug 28, 2005 3:39 pm
Location: Taiwan
To artem:
Thank you!!!
I have accepted!!!!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I think your code is right. N>=6 So, there is no "Goldbach's conjecture is wrong.". And your printing is wrong...

Code: Select all

``````     if(flag)
printf("%llu = %llu +%llu\n",N,x,primal);``````
But it should be..

Code: Select all

``````     if(flag)
printf("%llu = %llu + %llu\n",N,x,primal);``````
Missing one space....
Ami ekhono shopno dekhi...
HomePage

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

### algo for has - 543

#include <stdio.h>
/* by Michal Koucky */
/* Used linear method - you count the number of expected 'enclosed'
expressions. After every operator E,... you expect one more expression
than before, N doesn't change the number of expected expressions,
p through z decreases the number of expected expressions by one (they
are enclosed expr). */

/**
r: 0 ok.
-1 syntax err
-3 eof
*/
{
char c;
int senc; /* number of expected (sub)sentences */

senc=1; /* you expect one enclosed expression */

while(1){

switch( c= getchar() )
{

case 'C':
case 'D':
case 'E':
case 'I':
if(senc)senc++;
case 'N':
if(!senc){ /* consume rest of line */
while(getchar()!='\n');
return -1;
}
break;

case '\n':
if(senc) return -1;
else return 0;
case EOF:
return -3;
default:
if( c < 'p' || c > 'z' || !senc){ /* consume rest of line */
while(getchar()!='\n');
return -1;
}
senc--;
}
}
return -1;
}

int main()
{
while(1)
{
{
case 0:
printf("YES\n");
break;
case -1:
printf("NO\n");
break;
case -3:
return 0;
}
}
} /* main */

prime *******************************
#include<stdio.h>
#include<math.h>
#include<string.h>

#define N 40000

long int p[N];

void prime()
{

long int i,j;
int flag;

memset(p,1,sizeof(p));
p[0]=0;
p[1]=0;
p[2]=1;

for(i=3;i*i<N;i+=2)
{

if(p==0)
continue;

for(j=i*i;j<N;j+=i)
p[j]=0;

}
}

int main()
{

long int n,i;
int flag;

prime();

while(1)
{
scanf("%ld",&n);
if(n==0)
break;

flag = 0;

for(i=1;i<n;i+=2)
{
if(p && p[n-i])
{
printf("%ld = %ld + %ld\n",n,i,n-i);
flag = 1;
//break;
}
}
if(!flag)
printf("Goldbach's conjecture is wrong.\n");
}

return 0;
}
Last edited by brianfry713 on Tue Jan 21, 2014 9:51 pm, edited 1 time in total.

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am

### 543 why WA pls help

hi
i cannot understand why i am faced WA again and again. i have not found any errors.plz help me such for unexpected condition.
my code is
#include<stdio.h>
#include<math.h>
void main()
{
long long num,num1,j,k,i,flag,aa,cc;
while(scanf("%lld",&num)!=EOF)
{
if(num==0)
break;
j=3;
aa:
num1=num-j;
flag=1;
for(i=2;i<=sqrt(num1);i++)
{
flag=1;
if(num1%i==0)
{
flag=0;
break;
}
}
if(flag==1)
{
if(num1+j==num)
printf("%lld = %lld + %lld\n",num,j,num1);
}
if(flag==0)
{
j=j+2;
if(j>num1)
{
printf("Goldbach conjecture is wrong.\n");
goto cc;
}
goto aa;

}
cc:

}

}

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:

### hey!

you can never get the unexpected condition. bcoz you are a modon!
----------newton

see the problem. there is the terminating condition is not EOF.
it is !=0.

best of luck.
bye

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:
always try to avoid using goto function.

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
thanx

md.samiullah[sami]
New poster
Posts: 1
Joined: Sun Aug 27, 2006 11:00 am

### 543

i have tried to solve Goldbachs conjecture.
but there is a WR
i just cant understand why WR.my code is given below

#include<stdio.h>
#include<math.h>
//#include<conio.h>

main()
{
long long int i,j,n,index,flag,gb,p;
int prime[10]={3,5,7,11,13,17,19,23,29,31};
//clrscr();
/*prime[0] = 2;*///prime[0]=3;//index=1;
//printf("Enter Range:");
while(1)
{ //index=1;
scanf("%lld",&gb);
if(gb!=0)

{
for(i=0;i<=9;i++)
{ // p=0;
n=gb-prime;
flag=1;

for(j=3;j<=sqrt(n);j+=2)
if(n%j==0) //if(i%prime[j]==0)
{
flag=0;
break;
}
if(flag==1)
{
printf("%lld =%d + %lld",gb,prime,n);
p++;
break;
}
// else
// break;

// prime[index++] = i;
}
}

/*for(i=0;i<=10;i++)
{ for(j=index-2;j>=index-11;j--)
if((prime+prime[j])==n)
{printf("%lld = %lld +%lld",n,prime,prime[j]);
break;}
if((prime+prime[j])==n)
break;
} } */
else
break; }
//getch();
}
samiullah

Bluefin
New poster
Posts: 20
Joined: Sat Jul 08, 2006 3:39 pm
Contact:
I've just solved this problem today !!
I do not look throught your code, but my algorithm is like this:

(1) use sieve of Eratosthnenes to find all the prime numbers up tp 1000000

(2) add the smallest prime number and the largest prime number which is smaller than n

(3) if the sum is equal to n, print them, else continue step 2

My ACC code cost about 0.8 second and used 1412 memory.
Not very efficient, but enough to solve this problem

Good luck !!
"It's nice to be important, but it's more important to be nice"

http://bluefintuna.wordpress.com/