543 - Goldbach's Conjecture

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ssavi
New poster
Posts: 28
Joined: Thu Nov 20, 2014 9:57 pm

Re: 543 - Goldbach's Conjecture

Post by ssavi » Fri Jan 09, 2015 10:32 am

I Used Sieve Method In Genrating Prime . But i am Getting TLE . I got the Verdict for 5 times . i dont Know How to get rid of it . Please help me . I am in a great TROUBLE . Here Is my Code . Please help . Thanks in Advance . :(

Code: Select all

#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<iostream>
long long int a[1000000];
long long int x[1000000];

using namespace std;

int main()
{
    long long int n, i, j, k, l, sum, p, max, c, b, check;
    while(scanf("%lld",&n)==1 && n!=0)
    {
        check=0;
        if(n==6)
            { printf("6 = 3 + 3\n");  check=1;}
        else if(n>6)
        {
          l=1; max=0;
          for(i=1;i<=n;i++)
            {
                x[i]=i;
            }
            x[1]=0; l=1;
            for(i=2;i<=sqrt(n);i++)
            {
              if(x[i]!=0)
              {
                for(k=2*i;k<=n;k=k+i)
                if(x[k]!=0)
                    x[k]=0;
               }
             }
            for(i=1;i<=n;i++)
            {
              if(x[i]!=0)
                  a[l++]=x[i];
            }
        l=l-1;
        for(i=1;i<=sqrt(l)+1;i++)
        {
            for(j=l;j>=sqrt(l)+1;j--)
            {
                sum = a[i]+a[j];
                if(sum==n)
                   {
                       k = abs(a[i]-a[j]);
                       if(k>max)
                       {
                           max=k;
                           b = a[i];
                           c = a[j];
                           check=1;
                       }
                   }
            }
        }
             printf("%lld = %lld + %lld\n", n, b, c);
      }
      if(check==0)
        printf("Goldbach's conjecture is wrong.\n");
    }
    return 0;
}
I know I am a Failure Guy . :(

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 543 - Goldbach's Conjecture

Post by brianfry713 » Fri Jan 09, 2015 9:02 pm

Read this thread.
Normally when using the Sieve you first precalculate all the primes needed.
Check input and AC output for thousands of problems on uDebug!

saniaTK
New poster
Posts: 1
Joined: Tue Mar 17, 2015 11:56 pm

Re: 543 - Goldbach's Conjecture

Post by saniaTK » Wed Mar 18, 2015 12:00 am

Can anybody tell me where am I getting wrong??

My submission gives WA.

Code: Select all

import java.util.*;
import java.io.*;

class Main{

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
	
		int number;
		boolean check;
	   
		try {
			Scanner scanner = new Scanner(new File("input.txt"));
			PrintWriter out = new PrintWriter(System.out);
			
			while(scanner.hasNextInt())
			{
				number = scanner.nextInt();
				
				if(number == 0) break;
				
				if(number%2==0 && number>=6 && number<100000){
					
					check = false;
					
					for(int i=3;i<=number;i+=2){
						if(isPrime(i)){ 
							check = isPrime(number-i);
							
							if(check){
								out.println(number+" = "+i+" + "+(number-i));
								break;
							}
						}
					}
					if(!check)
						out.println("Goldbach's conjecture is wrong.");
				}
			}
			out.flush();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	static boolean isPrime(int n){
		
		for(int i=2;i<=Math.sqrt(n);i++){
			if(n%i==0)
				return false;
		}
		return true;
	}
}
Last edited by brianfry713 on Mon Mar 30, 2015 11:53 pm, edited 1 time in total.
Reason: Added code block

Lim.YuDe
New poster
Posts: 15
Joined: Sat Dec 13, 2014 1:32 pm

Re: 543 - Goldbach's Conjecture

Post by Lim.YuDe » Thu Apr 23, 2015 3:06 am

The input is up until 1000000 (10^6) but your code takes input until 100000 (10^5) only.

quanghm
New poster
Posts: 5
Joined: Sat Apr 25, 2015 4:00 pm

Re: 543 - Goldbach's Conjecture

Post by quanghm » Tue Apr 28, 2015 4:50 am

My code complies and runs fine with Mingw but got a compile error, can someone help me with this?

Code: Select all

#include <iostream>
#include <vector>
#include <string>
#include <stdio.h>

using namespace std;
int main() {
	int n=1000000;
	bool a[1000000] = {0}; // if i is check
	int i = 2;
	do {
		while(a[i]&&(i<n)){i++;}
		for (int j = 2 * i; j < n; j += i) { // kill multiple of i
					a[j] = true;
				}

	} while ((++i< n) && (a[i]));


	while (scanf("%d",&n)) {
		if (n==0){return 0;}
		i=n-1;
		while (i--){
			if (!(a[i]||a[n-i])){
				cout << n<<" = "<< n-i<<" + "<< i<<endl;
				break;
			}
		}
	}

}

Post Reply

Return to “Volume 5 (500-599)”