All Tracks Math Number Theory Basic Number Theory-2 Problem

Hacker Decrypting Messages
Tag(s):

Easy-Medium, Mathematics, Number theory

Problem
Editorial
Analytics

Alex has started hacking websites, and also started learning encryption and decryption of messages. Once he faced an interesting issue, where he needs to decrypt the message in a different way.
Initially, he will be given an array A of N integers, and has to decrypt Q messages. In each message he will get an integer X, and if X can be converted into product of two different or same prime numbers, then the real message is "YES" (without quotes), otherwise the message is "NO" (without quotes).

To convert X, he can choose one element from array say Y (X should be divisible Y), and can divide X by Y any number of times (till X is divisible by Y). Help Alex in decrypting the messages.

Input Format:

First line will contain an integer N and Q,, denoting the number of elements in the array and number of encrypted messages respectively.

Next line will contain N space-separated integers representing the elements of the array.

In next Q lines, each line will contain an integer X , representing an encrypted message.

Output Format:

For each encrypted message, output the decrypted message in new line.

Constraints:
\(1 \le N \le 10^5 \)
\( 0 \le A_i \le 10^6\)
\( 1 \le Q \le 10^6 \)
\( 0 \le X \le 10^6 \)

SAMPLE INPUT
4 3
2 22 7 10
16
429
42

SAMPLE OUTPUT
YES
NO
YES
Explanation

For \(X = 16\),
We can choose 2 from the given array and divide X by 2 , two times, which will result in 4.
As, \( 4 = 2 \times 2\). So answer is YES.

For \(X=429\), we can't choose any number from the array by using which we can convert X in product of two primes. So answer is NO.

For \(X = 42\),
We can choose 2 from the given array and divide X by 2 only one time, which will result in \(21\).
As, \(21 = 7 \times 3\). So answer is YES.

Time Limit: 3,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

IndiaHacks 2017: Programming

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?