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

Fuad Hassan EWU
New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

### hi

I am having TLE in this problem. Is my algo too slow. Or some where this code is falling in infinite loop??

Code: Select all

``````AC
``````
Last edited by Fuad Hassan EWU on Sun Oct 28, 2007 5:00 pm, edited 1 time in total.
Eagle er moto daana meley urbo
sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
-> give up intilize
-> Generate pair for each input number

-> I think you get TLE because you generate output for each num from
1 to 1000000.

Thanks
Keep Posting
Sapnil
"Dream Is The Key To Success"

@@@ Jony @@@
Fuad Hassan EWU
New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

### hi

sapnil wrote
-> give up intilize
-> Generate pair for each input number

-> I think you get TLE because you generate output for each num from
1 to 1000000.
But sapnil i stored pair from 6 to 1000009 in the structure. Later i used the input'th index of the structure array x. yes i generated output for 6 to 1000009. but it is pre-calculation. when i take input then i didn't calculate form 6 to 1000009. i only showed the pair in the input'th index of the array x.

plz keep posting and make me clear. thanks
Eagle er moto daana meley urbo
Fuad Hassan EWU
New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

### ..

O yes sapnil i got your point and get AC. that i skip all the odd numbers. thank u.
Eagle er moto daana meley urbo
hridoy
New poster
Posts: 21
Joined: Tue May 08, 2007 10:30 am
Location: Dhaka
Contact:

### TLE in acm-543

Can any one please tell me why I m getting TLE??

and How can I use sieve in such a long number 1000000..?

[codeAC[/code]
Last edited by hridoy on Fri Jan 04, 2008 9:51 pm, edited 1 time in total.
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
1. You can calculate the primes and store them before taking the input.
2. sqrt() is a slow function. So, you can use

Code: Select all

``````int P = sqrt(i);
for(j=3;j<=P;j+=2)``````
Hope these help.
hridoy
New poster
Posts: 21
Joined: Tue May 08, 2007 10:30 am
Location: Dhaka
Contact:

### acm-543 TLE

Thanks to Jan, My answer has improved but still I m getting TLE:(.. it's not working for input 1000000..
anymore suggestion form anybody???
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
You should post your new code.
hridoy
New poster
Posts: 21
Joined: Tue May 08, 2007 10:30 am
Location: Dhaka
Contact:

### 543 TLE

[/code]#include<stdio.h>
#include<math.h>

main()
{
long n,k=0,i,j,l,m,a,p,z,news;
while(1)
{

for(i=3;i<=n;i+=2)
{
z=0;
news=sqrt(i);
for(j=3;j<=news;j+=2)
if(i%j==0)
{
z=1;
break;
}
if(z==0)
{
a[k]=i;
k++;
}
}
scanf("%ld",&n);
if(n==0)
break;

p=0,l=0,m=0;

for(i=0;i<k;i++)
for(j=i;j<k;j++)
if(a+a[j]==n&&(l-m)<=(a[j]-a))
{
m=a;
l=a[j];
p=1;
}
if(p==1)
printf("%ld = %ld + %ld\n",n,m,l);
else
printf("Goldbach's conjecture is wrong.\n");
}
}
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
You didn't get my point. I was talking about..

Code: Select all

``````int main()
{
generate_Primes_upto_Limit();
whlie(input())
{
...
}
return 0;
}``````
Hope it helps.
hridoy
New poster
Posts: 21
Joined: Tue May 08, 2007 10:30 am
Location: Dhaka
Contact:

### TLE .......543

I m still TLE..but it's work for all critical i/0..
here is my code.

Code: Select all

``````AC
``````
Last edited by hridoy on Fri Jan 04, 2008 9:53 pm, edited 1 time in total.
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Code: Select all

``````      for(i=0;i<k;i++)
for(j=i;j<k;j++)``````
This is the reason for TLE.

Code: Select all

``````for(i=0;i<k;i++)
p = n-a[i];
use binary search to find p``````
Since the difference should be minimum, you can start your search form i to 0, where a <= n/2 and a is maxium. You can break the loop if you find a solution. Hope these help.
Ahmad
New poster
Posts: 16
Joined: Thu Apr 28, 2011 10:48 pm

### 543

someone tell me why am getting wrong answer or i will sucide
here's the java code

Code: Select all

``````import java.util.Scanner;

public class Main{
public static void main(String[] args) {
int r = 1000000;
boolean[] visited = new boolean[r+1];
for (int i = 2; i  < r; i++) {
if (!visited[i]) {
for (int j = 2; i * j < r; j++) {
visited[i * j] = true;
}
}
}
Scanner in = new Scanner(System.in);
int n = -1;
while ((n = in.nextInt()) != 0) {
if (!visited[n])
System.out.println("Goldbach's conjecture is wrong.");
else {
boolean found = false;
for (int i = 2; i < n; i++) {
int j = n - i;
if (j!= 1 && j != i && !visited[i] && !visited[j]) {
System.out.printf("%d = %d + %d\n", n, i, j);
found = true;
break;
}
}
if (!found)
System.out.println("Goldbach's conjecture is wrong.");
}
}
}
}
``````
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 543

Use the search option located at the top right corner to find existing discussions.
Don't create a new thread for a problem that already exists! Make your post on an existing one.
meee...
New poster
Posts: 4
Joined: Tue Dec 09, 2008 4:04 pm

### Re: 543-goldbach's conjecture..WHY AM I GETTING TLE??

Why am i getting TLE?

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

#define MSG(a) cout<<#a<<"="<<a<<endl;
#define MAX 1000001

int prime[MAX];
void sieve(int n){
for(int i = 0;i<=n;i++){
prime[i]=1;
}

prime=prime=0;

for(int i = 2;i*i<=n;i++){
if(prime[i]){
for(int j = i;j*i<=n;j++){
prime[i*j]=0;
}
}
}
}

int main(){
int n;
sieve(MAX-1);
//for(int i = 0;i<20;i++)MSG(prime[i]);
while(scanf("%d",&n) && n){
int dist = -1;
int ini=-1,end=-11;
for(int i = 2;i<=n/2;i++){
if(prime[i] && prime[n-i] && dist<abs(n-i-i)){
dist = abs(n-i-i);
ini = i;
end = n-i;
}
}

if(dist==-1){printf("Goldbach's conjecture is wrong.\n");continue;}
printf("%d = %d + %d\n",n,ini,end);
}
return 0;
}
``````