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

Post by Fuad Hassan EWU »

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 »

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

Post by Fuad Hassan EWU »

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

..

Post by Fuad Hassan EWU »

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 »

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 »

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 »

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 »

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 »

[/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 »

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 »

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 »

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 »

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

Post by sohel »

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

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)”