543 - Goldbach's Conjecture
Moderator: Board moderators
543 - Goldbach's Conjecture
#include<iostream.h>
#include<math.h>
int main()
{
int prime[1000000]={0};
prime[2]=1;
prime[3]=1;
for(long k=5;k<1000000;k+=2)
{
int a=0;
for(long l=3;l<k;l+=2)
{
if(prime[l]==1)
{
if(k%l==0)
{
a=1;
break;
}
if(prime[l]>(long)(sqrt(k)+0.5))break;
}
}
if(a==0)prime[k]=1;
}
long n;
while(cin>>n&&n>0)
{
long a=0,b=0;
for(long m=3;m<=n/2;m+=2)
{
if(prime[m]==1)
{
long q=n-m;
if(prime[q]==1)
{
a=m;
b=q;
break;
}
}
}
if(a!=0&&b!=0)
cout<<n<<" = "<<a<<" + "<<b<<"\n";
else
cout<<"Goldbach's conjecture is wrong.\n";
}
return 0;
}
#include<math.h>
int main()
{
int prime[1000000]={0};
prime[2]=1;
prime[3]=1;
for(long k=5;k<1000000;k+=2)
{
int a=0;
for(long l=3;l<k;l+=2)
{
if(prime[l]==1)
{
if(k%l==0)
{
a=1;
break;
}
if(prime[l]>(long)(sqrt(k)+0.5))break;
}
}
if(a==0)prime[k]=1;
}
long n;
while(cin>>n&&n>0)
{
long a=0,b=0;
for(long m=3;m<=n/2;m+=2)
{
if(prime[m]==1)
{
long q=n-m;
if(prime[q]==1)
{
a=m;
b=q;
break;
}
}
}
if(a!=0&&b!=0)
cout<<n<<" = "<<a<<" + "<<b<<"\n";
else
cout<<"Goldbach's conjecture is wrong.\n";
}
return 0;
}
don't make so big arrays on the stack (in this case prime is 4Mb). make it a global variable. btw your prime searching algo is not effective for this problem, it's way too slow. try another algorithm, for example sieve http://www.fpx.de/fp/Software/Sieve.html. why use 'int' for a huge boolean array? it allocates 4x memory. btw there is another similar problem P10311...
543 WA
Could help me? I don't know what's wrong with it?
or give me some input?
or give me some input?
Code: Select all
var
tab:array[1..1000000]of longint;
wyn:array[1..50000]of byte;
n,a,nr,b:longint;
czy:boolean;
begin
tab[1]:=2;
nr:=2;
fillchar(wyn,sizeof(wyn),0);
for a:=2 to 1000000 do
tab[a]:=maxlongint;
for a:=3 to 1000000 do
begin
b:=1;
czy:=true;
while tab[b]<=round(sqrt(a)) do
begin
if a mod tab[b]=0 then czy:=false;
inc(b);
end;
if czy then
begin
inc(wyn[a]);
tab[nr]:=a;
inc(nr);
end;
end;
readln(n);
while n<>0 do
begin
b:=2;
czy:=true;
while (tab[b]<=n div 2)and(czy) do
begin
if wyn[n-tab[b]]=1 then
begin
writeln(n,' ','=',' ',tab[b],' ','+',' ',n-tab[b]);
czy:=false;
end;
inc(b);
end;
if czy then
begin
write('Goldbach');
write(chr(39));
writeln('s conjecture is wrong.');
end;
readln(n);
end;
end.
543 why wa .......
i am having wa all the time in 543 . am i missing some thing ? my algorithm for this problem is verys easy .
1) generate prime according to the stipulated range .
2)start searching the array of primes like this .let a prime be "A" ,where prime=="A" and the number which is to be shown as the sum of two primes is "X".now check if "B" is prime . where B = X - A. if yes X=A +B.else i++;
here is my code . pliz check it for me .
[c]#include<stdio.h>
#include<math.h>
#define MAX 1000000
long int PrimeNumber[MAX];
long int Count;
void GeneratePrime()
{
long int num,j;
PrimeNumber[0]=2;
PrimeNumber[1]=3;
PrimeNumber[2]=5;
PrimeNumber[3]=7;
Count=4;
for(num=11;num<MAX;num=num+2)
{
for(j=0;j<sqrt(PrimeNumber[Count-1]);j++)
if(num%PrimeNumber[j]==0)
break;
if(j==Count)
PrimeNumber[Count++]=num;
}
}
int isPrime(long int n){
long int i ;
if(n==0L || n==1L)
return 0;
for(i=2;i<=sqrt(n);i++){
if((n%i)==0)
return 0;
else
continue;
}
return 1;
}
void GoldBachConjecture(long int x){
long int i;
long int y,z;
int flag,check;
check=0;
for(i=0;i<Count;i++){
y=PrimeNumber;
if(y>x)
break;
z=x-y;
flag=isPrime(z);
if(flag==1){
printf("%ld = %ld + %ld\n",x,y,z);
check=1;
return;
}
else
continue;
}
if(check==0)
printf("Goldbach's conjecture is wrong.\n");
}
int main(){
long int x;
GeneratePrime();
while(scanf("%ld",&x)==1){
if(x==0L)
break;
GoldBachConjecture(x);
}
return 0;
}[/c]
plizzzz help me in this . i have tried many different things . but failed.
Bye
Riyad
1) generate prime according to the stipulated range .
2)start searching the array of primes like this .let a prime be "A" ,where prime=="A" and the number which is to be shown as the sum of two primes is "X".now check if "B" is prime . where B = X - A. if yes X=A +B.else i++;
here is my code . pliz check it for me .
[c]#include<stdio.h>
#include<math.h>
#define MAX 1000000
long int PrimeNumber[MAX];
long int Count;
void GeneratePrime()
{
long int num,j;
PrimeNumber[0]=2;
PrimeNumber[1]=3;
PrimeNumber[2]=5;
PrimeNumber[3]=7;
Count=4;
for(num=11;num<MAX;num=num+2)
{
for(j=0;j<sqrt(PrimeNumber[Count-1]);j++)
if(num%PrimeNumber[j]==0)
break;
if(j==Count)
PrimeNumber[Count++]=num;
}
}
int isPrime(long int n){
long int i ;
if(n==0L || n==1L)
return 0;
for(i=2;i<=sqrt(n);i++){
if((n%i)==0)
return 0;
else
continue;
}
return 1;
}
void GoldBachConjecture(long int x){
long int i;
long int y,z;
int flag,check;
check=0;
for(i=0;i<Count;i++){
y=PrimeNumber;
if(y>x)
break;
z=x-y;
flag=isPrime(z);
if(flag==1){
printf("%ld = %ld + %ld\n",x,y,z);
check=1;
return;
}
else
continue;
}
if(check==0)
printf("Goldbach's conjecture is wrong.\n");
}
int main(){
long int x;
GeneratePrime();
while(scanf("%ld",&x)==1){
if(x==0L)
break;
GoldBachConjecture(x);
}
return 0;
}[/c]
plizzzz help me in this . i have tried many different things . but failed.
Bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN
-
- Learning poster
- Posts: 94
- Joined: Sat Oct 05, 2002 5:34 pm
- Location: CS - AIUB, Dhaka, Bangladesh.
- Contact:
Check it
Maartin, I didn't use Sieve and it really doesn't matter in this problem, no chance to get TLE. (And also, you should not talk like this)Maarten wrote:Also, I am surprised you don't get TLE. Your method of generating primes and checking for primality is very inefficient. Have you ever heard of Erasthostenes Sieve (how the hell do you write it??)
Riyad, your this condition never comes true, since you are not counting j 0 to count-1
Code: Select all
if(j==Count) /* Contradiction */
PrimeNumber[Count++]=num;
Change the code as follows: [c] for(j=0,f=1;j<=sqrt(PrimeNumber[Count-1]);j++)
if(num%PrimeNumber[j]==0)
{
f=0;
break;
}
if(f) PrimeNumber[Count++]=num; [/c]
Sajid Online: www.sajidonline.com
right u r
martin and sajid thanx to both of u for replying . yes i realised my mistake in the generating prime function . the function dont really stop . that means 2 3 5 7 are the only primes generated . i got tle in the problem 543 . my way of generating prime is really slow . i have faced this prob for a long time .(the need of an efficient algorithm for generating prime )can any one of u provide me a efficient algo for generating prime , if u people dont really face any prob.
**** sajid i made the correction u asked me to do . i did with no success . got TLE in the prob.
++++ martin , as a matter of regret i heard about the algorithm sieve of Erasthostenes. but i dont feel tempted to write one my self . and i also know how the algorithm works.
thanx any way
Riyad
**** sajid i made the correction u asked me to do . i did with no success . got TLE in the prob.
++++ martin , as a matter of regret i heard about the algorithm sieve of Erasthostenes. but i dont feel tempted to write one my self . and i also know how the algorithm works.
thanx any way
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN
-
- Learning poster
- Posts: 94
- Joined: Sat Oct 05, 2002 5:34 pm
- Location: CS - AIUB, Dhaka, Bangladesh.
- Contact:
Your GeneratePrimes() function seems ok, but u have to have faster IsPrime( ) function...
you are doing mod by all the numbers , but why ? and also even numbers
you can mod with only prime numbers that is alreay in your PrimeNumber[ ] array.
GoldBachConjecture( ) function needs the same thing.
Try...
you are doing mod by all the numbers , but why ? and also even numbers
you can mod with only prime numbers that is alreay in your PrimeNumber[ ] array.
GoldBachConjecture( ) function needs the same thing.
Try...
Sajid Online: www.sajidonline.com
-
- New poster
- Posts: 10
- Joined: Thu Jun 05, 2003 5:23 pm
- Location: CS, AIUB, Dhaka, Bangladesh
- Contact:
What a way of talking!!!!Have you ever heard of Erasthostenes Sieve (how the hell do you write it??)
[c]int isPrime(unsigned long long p)
{
unsigned long long i;
for(i=2;i<=sqrt(p);i++)
if(!(p%i))
return 0;
return 1;
}[/c]
Trust me, this function is enough for this problem, whenever you need to check if a number is prime or not just call it. You don't even need to generate all the primes in an array. Anyway, I haven't seen your code yet.
Hope it helps.
hey thanx
hey thanx sajid and saqib
i did not realize how i could optimize my isPrime Function . but afetr readind u r post , i found out how to optimize it .
1)mod the number with the primes i generated (the fastest method)
2)mod the number with only odd numbers
i ll try to correct my code and let u people know what have happened .
thanx once again
i did not realize how i could optimize my isPrime Function . but afetr readind u r post , i found out how to optimize it .
1)mod the number with the primes i generated (the fastest method)
2)mod the number with only odd numbers
i ll try to correct my code and let u people know what have happened .
thanx once again
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN
-
- New poster
- Posts: 23
- Joined: Sat Oct 04, 2003 12:12 pm
- Location: in Your Heart ^^
- Contact:
hi... can any body help me ?
i still got WA for 543... is there any tricky input ? i've checked my output with my friend's code (she got AC-ed) and its ok, here is my code :
i still got WA for 543... is there any tricky input ? i've checked my output with my friend's code (she got AC-ed) and its ok, here is my code :
Code: Select all
[c]
#include <stdio.h>
#include <math.h>
long angka;
long mulai;
int ok;
long genPrime(void)
{
long a;
long b;
long batas;
int prime;
for (a=mulai;;a+=2)
{
batas=sqrt(a)+1;
prime=1;
for (b=2;b<batas;b++)
{
if (a%b==0)
{
prime=0;
break;
}
}
if (prime==1) return a;
}
}
int isPrime(long cek)
{
long a;
long batas;
batas=sqrt(cek)+1;
for(a=2;a<batas;a++)
{
if (cek%a==0) return 0;
}
return 1;
}
void main()
{
long a1,a2;
#ifndef ONLINE_JUDGE
freopen ("543.in","r",stdin);
freopen ("543.out","w",stdout);
#endif
while (scanf ("%ld ",&angka)!=EOF)
{
if (angka==0) break;
mulai=3;
ok=0;
do
{
a1=genPrime();
if (a1>=angka) break;
a2=angka-a1;
ok=isPrime(a2);
mulai+=2;
}while (ok!=1);
if (ok==1)
{
printf ("%lld = %lld + %lld\n",angka,a1,a2);
}
else
{
printf ("Goldbach's conjecture is wrong.\n");
}
}
}
sorry for the messy code... please help me...[/c]
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...
May every person helps each other and creates a world full of joy...
-
- New poster
- Posts: 23
- Joined: Sat Oct 04, 2003 12:12 pm
- Location: in Your Heart ^^
- Contact:
OH MY GOD !!!! you're right!!! i got AC now.... how can i be so careless ??? i have trace it for about 3 days and comparing 3MB sample input + 11 MB sample output manually...... and its... its just about %lld ....
btw, thanx a lot.... so this night i can sleep tight ....
btw, thanx a lot.... so this night i can sleep tight ....
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...
May every person helps each other and creates a world full of joy...
What's faster -- C/C++ or Pascal ?
Hi everybody,
I use Pascal OBVIOUSLY
But ... trying to solve 543 - Goldbach's conjecture , I visited Steven Halim's website and it was written that I may store all primes in an array and do it with Brute Force [ if you know the problem ] . I did it [ in Pascal , I checked for every number lower than limit if it's prime * ] , and got TLE :/ Although it was written that this algorithm works ! Then I thought , C/C++ is faster than Pascal . Furthermore , when I look through the stats of some problems , rarely there is any person using Pascal within first ... er ... 10 times ? Usually , an algorithm implementated in C/C++ runs faster than the one in Pascal . Am I right ? If so , why is it like that ?
_____________________________________________________________
* Of course, for every n > 4 , I check if any prime i from 2 to sqrt (n) divides n , until I have found one that does or i have reached sqrt (n) -- can you think of any better algorithm ?
I use Pascal OBVIOUSLY
But ... trying to solve 543 - Goldbach's conjecture , I visited Steven Halim's website and it was written that I may store all primes in an array and do it with Brute Force [ if you know the problem ] . I did it [ in Pascal , I checked for every number lower than limit if it's prime * ] , and got TLE :/ Although it was written that this algorithm works ! Then I thought , C/C++ is faster than Pascal . Furthermore , when I look through the stats of some problems , rarely there is any person using Pascal within first ... er ... 10 times ? Usually , an algorithm implementated in C/C++ runs faster than the one in Pascal . Am I right ? If so , why is it like that ?
_____________________________________________________________
* Of course, for every n > 4 , I check if any prime i from 2 to sqrt (n) divides n , until I have found one that does or i have reached sqrt (n) -- can you think of any better algorithm ?
kiha
Re: What's faster -- C/C++ or Pascal ?
That's a really slow algorithm. Read on sieve.kiha wrote:* Of course, for every n > 4 , I check if any prime i from 2 to sqrt (n) divides n , until I have found one that does or i have reached sqrt (n) -- can you think of any better algorithm ?
Saludos,
HoraPe