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

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

hi

Post by Fuad Hassan EWU » 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
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:

Post by sapnil » 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
"Dream Is The Key To Success"

@@@ Jony @@@

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

hi

Post by Fuad Hassan EWU » 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
Eagle er moto daana meley urbo

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

..

Post by Fuad Hassan EWU » 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.
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

Post by hridoy » 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]
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:

Post by Jan » 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.

hridoy
New poster
Posts: 21
Joined: Tue May 08, 2007 10:30 am
Location: Dhaka
Contact:

acm-543 TLE

Post by hridoy » 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???

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Dec 17, 2007 12:35 am

You should post your new code.

hridoy
New poster
Posts: 21
Joined: Tue May 08, 2007 10:30 am
Location: Dhaka
Contact:

543 TLE

Post by hridoy » 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");
}
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » 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.

hridoy
New poster
Posts: 21
Joined: Tue May 08, 2007 10:30 am
Location: Dhaka
Contact:

TLE .......543

Post by hridoy » 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
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:

Post by Jan » 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.

Ahmad
New poster
Posts: 16
Joined: Thu Apr 28, 2011 10:48 pm

543

Post by Ahmad » 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.");
			}
		}
	}
}

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 543

Post by sohel » 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.

meee...
New poster
Posts: 4
Joined: Tue Dec 09, 2008 4:04 pm

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

Post by meee... » 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;
}

Post Reply

Return to “Volume 5 (500-599)”