Return two primes [HARD/IMP] (Goldbach’s conjecture)

Company: Zoho, Yahoo

Question:

Given an even number ( greater than 2 ), return two prime numbers whose sum will be equal to given number. There are several combinations possible. Print only first such pair. 

NOTE: A solution will always exist, read Goldbach’s conjecture.

Also, solve the problem in linear time complexity, i.e., O(n).

Input:

The first line contains T, the number of test cases. The following T lines consist of a number each, for which we'll find two prime numbers.

Note: The number would always be an even number.

 
Output:

For every test case print two prime numbers space separated, such that the smaller number appears first. Answer for each test case must be in a new line.

Constraints:

1 ≤ T ≤ 70
1 ≤ N ≤ 10000

Example:

Input:

5
74
1024
66 
8
9990

Output:

3 71
3 1021
5 61
3 5
17 9973

CODE:

import java.util.*;

import java.lang.*;

import java.io.*;

class GFG {

public static void main (String[] args) {

Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        while(t-->0) {

            int n = sc.nextInt();

    boolean[] primes = allPrimes(n);

    boolean found = false;

    for(int i = 3; i < n; i++) {

        if(primes[i]) {

                    if(primes[n-i]) {

                                found = true;

                         System.out.println(i + " " + (n-i));

                         break;

                        }

              if(found) {

                 break;

             }

        }

    }

}

}

public static boolean[] allPrimes(int n) {

    boolean[] primes = new boolean[n+1];

for(int i = 0; i <= n; i++) {

    primes[i] = true;

}

primes[0] = false;

primes[1] = false;

for(int i = 2; i < Math.sqrt((double)n); i++) {

    if(primes[i] == true) {

        for(int j = i*i; j <= n; j = j + i){

                primes[j] = false;

        }

    }

}

return primes;

}

}

EXECUTION TIME:0.11s