543 - Goldbach's Conjecture

[ssavi]

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

[brianfry713]

Read this thread.
Normally when using the Sieve you first precalculate all the primes needed.

[saniaTK]

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

[Lim.YuDe]

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

[quanghm]

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

}