Page 3 of 8
543 why WA
Posted: Tue Aug 02, 2005 8:44 pm
by 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]
543 WA, i need help
Posted: Thu Aug 18, 2005 8:00 am
by 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;
}
Accepted 543
Posted: Fri Aug 19, 2005 4:29 am
by 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;
}
}
543
Posted: Sun Aug 28, 2005 3:44 pm
by georgemouse
I got tle but I don't know how to make it faster!!
Can someone help me?
thanks!!!!
Here is my code:
Posted: Sun Aug 28, 2005 6:57 pm
by 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)
Posted: Sun Aug 28, 2005 7:57 pm
by 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?
Posted: Wed Aug 31, 2005 1:26 pm
by georgemouse
To artem:
Thank you!!!
I have accepted!!!!
Posted: Tue Nov 22, 2005 1:54 pm
by 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....
algo for has - 543
Posted: Sat Jul 01, 2006 8:53 pm
by 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;
}
543 why WA pls help
Posted: Sat Aug 19, 2006 12:34 pm
by 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:
}
}
hey!
Posted: Sat Aug 19, 2006 2:31 pm
by 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
Posted: Sat Aug 19, 2006 2:38 pm
by newton
always try to avoid using goto function.
bcoz it is bad programming.
Posted: Sat Aug 19, 2006 2:52 pm
by ishtiaq ahmed
thanx
543
Posted: Sun Aug 27, 2006 11:15 am
by 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();
}
Posted: Sun Aug 27, 2006 12:07 pm
by 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 !!
