FilesExpand file tree

 master

/

B.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

64 lines (52 loc) · 1.06 KB

 master

/

B.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

64 lines (52 loc) · 1.06 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

#include <iostream>

#include <algorithm>

#include <vector>

#include <cmath>

#include <string.h>

using namespace std;

const int M = 1100000;

bool mark[M];

int N;

long long int data[M];

int prime_nums[M];

int cnt = 0;

void sieve_prime(){

memset(mark, true, sizeof(mark));

mark[0] = mark[1] = false;

for(int i=2; i<=sqrt(M); i++){

if(mark[i]){

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

mark[j]=false;

}

}

}

}

void work(){

sieve_prime();

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

if(mark[i]){

prime_nums[cnt++] = i;

}

}

vector< long long int > nums;

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

long long int t = prime_nums[i];

nums.push_back( t*t );

}

sort(nums.begin(), nums.end());

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

if(binary_search( nums.begin(), nums.end(), data[i])){

cout<<"YES"<<endl;

}else{

cout<<"NO"<<endl;

}

}

}

int main(){

cin>>N;

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

cin>>data[i];

}

work();

return 0;

}