543 - Goldbach's Conjecture

[rocky11]

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

[esmitt]

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

Thanks in advance.

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]

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

[georgemouse]

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

[artem]

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]

To artem:
Your code really works!!

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

[georgemouse]

To artem:
Thank you!!!
I have accepted!!!!

[Jan]

I think your code is right. N>=6 So, there is no "Goldbach's conjecture is wrong.". And your printing is wrong...

Your code....

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

[sakhassan]

#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). */

int read_sen()
/**
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)
{
switch(read_sen())
{
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;
}

[ishtiaq ahmed]

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]

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]

always try to avoid using goto function.
bcoz it is bad programming.

[ishtiaq ahmed]

thanx

[md.samiullah[sami]]

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


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

[Bluefin]

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