T-primes · Interview Problem

Back to problems

Codeforces

Medium

Number Theory

Math

Arrays

T-primes

Determine for each number whether it is a square of a prime number.

Acceptance 0%

Start Practice

Problem Statement

Problem

You are given several integers. For each integer $x$ , decide whether it is a T-prime.

A number is called T-prime if it has exactly three positive divisors. A useful fact is that a number is T-prime if and only if it is the square of a prime number.

For every query, output YES if the number is T-prime, otherwise output NO.

Notes

A number with exactly three divisors must be of the form $p^2$ , where $p$ is prime.
You need to answer each query independently.

Input Format

The first line contains an integer $n$ — the number of queries.
The second line contains $n$ integers $x_1, x_2, \dots, x_n$ .

Output Format

Print $n$ lines.
For each $x_i$ , print YES if it is a T-prime, otherwise print NO.

Constraints

$1 \le n \le 10^5$
$1 \le x_i \le 10^{12}$

Examples

Sample cases returned by the problem API.

Example 1

Input

3
4 5 9

Output

YES
NO
YES

Explanation

$4 = 2^2$ and $2 $is prime, so it is T-prime. \$ 5 $is not a perfect square.$ 9 = 3^2 $and \$ 3$ is prime, so it is T-prime.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress