## 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

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

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

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

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

}``````