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
Code: Select all
AC
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.-> 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.
Code: Select all
int P = sqrt(i);
for(j=3;j<=P;j+=2)
Code: Select all
Code: Select all
int main()
{
generate_Primes_upto_Limit();
whlie(input())
{
...
}
return 0;
}
Code: Select all
AC
Code: Select all
for(i=0;i<k;i++)
for(j=i;j<k;j++)
Code: Select all
for(i=0;i<k;i++)
p = n-a[i];
use binary search to find p
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.");
}
}
}
}
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;
}