Check where the integers are Tprime or not The objective of the code is to check the given inputs are tprime or not.

Example:

3 //no of integers(1 ≤ n ≤ 10^5)
4 5 6 //space-separated integers xi (1 ≤ xi ≤ 10^12)


Output:

YES
NO
NO


The code works fine but always exceeds time limit 2000ms. How to reduce it?

import java.util.Scanner;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class TprimePractise {

public static void main(String[] args) throws Exception {
BufferedReader br = 
new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
int input = Integer.valueOf(line);
line = br.readLine();
long sqrt, x;
for (String num : line.split("\\s")) {
    x = Long.valueOf(num);

    if (x == 1) {
        System.out.println("NO");
        continue;
    }
    sqrt = (long) Math.sqrt(x);
    if (sqrt * sqrt == x &amp;&amp; isPrime(sqrt)) {
        System.out.println("YES");
    } else {
        System.out.println("NO");
    }

  }
}

public static boolean isPrime(long num) {

for (int j = (int) num / 2; j &gt;= 2; j--) {
    if (num % j == 0) {
        return false;
    }
}
return true;
 }

}
Change your algorithm

Currently, for each of \$10^5\$ numbers, you do a trial division loop that could check up to \$N/2\$ numbers, where \$N\$ can be as big as \$10^{12}\$.  This means that your program may require as many as \$10^{17}\$ operations.

You will certainly need to do better than that to finish within 2 seconds.

Proposal #1

The simplest way to speed up your program is to change your trial division loop.  I would make the following changes:


Check for divide by 2 as a special case before the loop.  In the loop, only check for division by odd numbers.
Make the loop go from small to large, as it is more likely that a random number will be divisible by a smaller number rather than a larger one.  In other words, start your loop at 3 and go up by 2 each loop.
Make the loop terminate at sqrt(n) instead of n/2.


Of the points above, #3 is the most important point.  This makes the trial division an \$O(\sqrt N)\$ operation instead of an \$O(N)\$ operation.  It reduces the max number of iterations from \$10^{12}\$ to \$10^6\$, making your total number of iterations in the worst case \$10^5 * 10^6 = 10^{11}\$.  So with this algorithm, the worst case probably wouldn't finish in 2 seconds, but the actual input might succeed.

Proposal #2

To make your program even faster, I would suggest the following:


Use the sieve of Eratosthenes to find all prime numbers from 2 to 10^6.  You can leave the output of the sieve as an array of booleans, telling you which numbers are prime.
Read in the input numbers.  For each input number, determine if it is a perfect square.  If it is, look up the square root of the input number in the array of booleans.  If the square root is prime, then the input number is a "tprime".


Part 1, the sieving part, takes around \$O(N * \log \log N)\$ time, where \$N\$ is 10^6, which means around \$4.3 * 10^6\$ steps.

Part 2 takes \$O(N)\$ time, where \$N\$ is 10^5, so around \$10^5\$ steps.

So the total of both parts comes out to roughly \$4.4 * 10^6\$ steps, which is much faster than proposal #1, and would definitely finish in under 2 seconds no matter what the input contained.

Thanks to maaartinus for suggesting the \$O(1)\$ lookup.