Page 5 of 8

### hi

Posted: Sat Oct 27, 2007 10:23 pm
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
``````

Posted: Sun Oct 28, 2007 4:00 pm
-> 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

### hi

Posted: Sun Oct 28, 2007 4:48 pm
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

### ..

Posted: Sun Oct 28, 2007 4:59 pm
O yes sapnil i got your point and get AC. that i skip all the odd numbers. thank u.

### TLE in acm-543

Posted: Sun Dec 16, 2007 11:16 am
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]

Posted: Sun Dec 16, 2007 1:58 pm
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.

### acm-543 TLE

Posted: Sun Dec 16, 2007 10:32 pm
Thanks to Jan, My answer has improved but still I m getting TLE:(.. it's not working for input 1000000..
anymore suggestion form anybody???

Posted: Mon Dec 17, 2007 12:35 am
You should post your new code.

### 543 TLE

Posted: Mon Dec 17, 2007 9:01 pm
[/code]#include<stdio.h>
#include<math.h>

main()
{
long n,k=0,i,j,l,m,a[200000],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");
}
}

Posted: Tue Dec 18, 2007 11:35 am
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.

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

Posted: Wed Dec 19, 2007 9:36 pm
I m still TLE..but it's work for all critical i/0..
here is my code.

Code: Select all

``````AC
``````

Posted: Thu Dec 20, 2007 11:26 am

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.

### 543

Posted: Sun May 01, 2011 7:32 pm
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.");
}
}
}
}
``````

### Re: 543

Posted: Sun May 01, 2011 11:17 pm
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.

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

Posted: Wed Oct 26, 2011 3:32 pm
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[0]=prime[1]=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;
}
``````