## 543 - Goldbach's Conjecture

Moderator: Board moderators

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

### Re: 543 - Goldbach's Conjecture

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

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

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.

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

### Re: 543 - Goldbach's Conjecture

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

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

}``````