Golu and Sweetness
Golu and his friend are busy preparing dishes for the winners of this contest. There are N dishes in the menu.
Golu assigns a sweetness factor to each dish. His friend is curious about this sweetness factor and decides to ask him Q queries about that.
In each query, he asks Golu to count the number of numbers in range [l,r] whose sweetness factor is a prime number.
Sweetness Factor of a number A is defined as the number of positive integers B, satisfying the following 2 conditions:
1 <= B <= A and
A * B = lcm(A,B)
First line consists of 2 integers, N and Q.
The next line contains N integers each representing a dish.
Then Q lines follow each containing 2 integers, l and r.
For each Query, output the number of numbers having sweetness factor as a prime number in a new line.
Constraints1 <= N,Q <= 100000
All the N numbers are positive integers between 0 and 1000000000
All the queries and the array indices are 1-based.
Input: 3 2 3 2 1 1 2 2 3 Output: 1 0
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions