543 - Goldbach's Conjecture

[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

[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

[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

[Fuad Hassan EWU]

O yes sapnil i got your point and get AC. that i skip all the odd numbers. thank u.

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

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

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]

You should post your new code.

[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");
}
}

Code: Select all

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

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

Code: Select all

AC

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

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]

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

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