## 543 - Goldbach's Conjecture

Moderator: Board moderators

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

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

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

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