@Darklordx/

TEMPLATE-35

Java

No description

fork
loading
Files
  • Main.java
Main.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
//TEMPLATE
import java.util.*;
import java.math.*;
public class Main {
    static Scanner scan;
    public static void println(Object s){System.out.println(s);}
    public static void print(Object s){System.out.print(s);}
    public static int nextInt(){return scan.nextInt();}
    public static long nextLong(){return scan.nextLong();}
    
    public static int nextIntL(){int i = scan.nextInt(); scan.nextLine(); return i;}
    public static long nextLongL(){long i = scan.nextLong(); scan.nextLine(); return i;}

    public static String nextLine(){return scan.nextLine();}
    
    static void printArray(int arr[]) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i]+" "); 
        System.out.println(); 
    }

    public static void main(String[] args) {scan = new Scanner(System.in);solution();}

    //Solution goes below:
    public static void solution(){
        //println(isPrime(999983));
        int n = nextInt();

        long[] All = sieve();
        int size = All.length-1;
        //println(size);
        for(int i=0; i<n;i++){
            long a = nextLong();
            long sqrt = (long)Math.sqrt((double)a);
            //println(sqrt);
            if(sqrt*sqrt==a){
                if(binarySearch(All, 0, size,sqrt)){
                    println("YES");
                }else{
                    println("NO");
                }
            }else{
                println("NO");
            }
            
        }
    }
    static boolean binarySearch(long[] arr, int l, int r, long x) 
    {
        //print(arr.get(arr.size()-1));
        //if(arr.get(arr.size()-1)==x){
        //    return true;
        //}
        if (r >= l) { 
            int mid = l + (r - l) / 2; 
  
            // If the element is present at the 
            // middle itself 
            if (arr[mid] == x) 
                return true; 
  
            // If element is smaller than mid, then 
            // it can only be present in left subarray 
            if (arr[mid] > x) 
                return binarySearch(arr, l, mid - 1, x); 
  
            // Else the element can only be present 
            // in right subarray 
            return binarySearch(arr, mid + 1, r, x); 
        } 
  
        // We reach here when element is not present 
        // in array 
        return false; 
    } 
    static long[] sieve() { 
        boolean prime[] = new boolean[1000001]; 
        for(int i=0;i<1000000;i++) 
            prime[i] = true; 
          
        for(int p = 2; p <=1000; p++){
            if(prime[p] == true) { 
                // Update all multiples of p 
                for(int i = p*p; i <= 1000000; i += p) 
                    prime[i] = false; 
            } 
        } 
        long[] res = new long[78498];
        int j = 0;
        for(int i = 2; i <= 1000000; i++) 
        { 
            if(prime[i] == true){
                res[j] = (long)i;
                j++;
            }
        } 
        return(res);
    }
    /*
    static long[] allPrimes(){
        long[] res = new long[78498]; // Size. :)
        int j=0;

        for(long i = 0 ; i<1000000; i++){
            if(isPrime(i)){
                res[j]=i;
                j++;
            }
        }
        return(res);
    }
    static boolean isPrime(long a){
        if(a<=1){
            return(false);
        }
        if(a==2||a==3||a==5||a==7){
            return(true);
        }
        if(a%2==0||a%3==0){
            return(false);
        }
        long max = (long)((Math.sqrt((double)a)+1)/6);
        for(int i = 1; i<=max; i++){
            if(a%(6*i-1)==0){
                return(false);
            }
            if(a%(6*i+1)==0){
                return(false);
            }
        }
        return(true);
    }
    */
}