Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef likes solving problems involving a lot of queries with prime numbers. One day, he found a new problem which is difficult for him to solve. So, he needs your help to solve it.
Given an array a of N integers and Q queries where each query provides you with four integers L, R, X and Y. 
For each query, output the value of F(L, R, X, Y) as defined below. 

F(L, R, X, Y) {

result := 0
for( i = X to i = Y )  {
if( isPrime(i) ) {
for( j = L to j = R ) {
number := a[j]
exponent := 0
while( number % i == 0 ) {
exponent := exponent + 1 
number := number/i
}
result := result + exponent
}
}
}
return result
}

isPrime(x) returns true if x is Prime otherwise false.

------ Input ------ 

First line of the input contains a single integer N denoting the number of elements in a given array.
Next line contains N integers separated by a space, which denotes a[1], a[2], ..., a[n]. 
Third line contains Q denoting the number of queries.
Next Q lines contain four integers L , R , X , Y   separated by a space.

------ Output ------ 

Output the value for each F(L, R, X, Y) in a separate line.

------ Constraints ------ 

$1 ≤ N, Q  ≤ 10^{5}$
$1 ≤ L ≤ R ≤ N $
$1 ≤ X ≤ Y ≤ 10^{6} $
$2 ≤ a[i] ≤ 10^{6} , where 1 ≤ i ≤ N $

------ Subtasks   ------ 

$Subtask #1 (10 points): 1 ≤ N, Q ≤ 100 $
$Subtask #2 (20 points): 1 ≤ N, Q ≤ 1000 $
$Subtask #3 (70 points): Original constraints $ 

----- Sample Input 1 ------ 
4 
2 3 4 5
2
1 3 2 3
1 4 2 5
----- Sample Output 1 ------ 
4
5
----- explanation 1 ------ 
Query 1 :
The first prime is 2. 2 divides the first element 1 time, 2 divides the second element 0 times and 2 divides the third element 2 times. Hence 2 contributes a total of 3 to the result ( 1 + 0  + 2 = 3 ) 

The second prime is 3. 3 divides the first element 0 times, 3 divides the second element 1 time and 3 divides the third element 0 times. Hence it contributes 1 to the result ( 0 + 1 + 0 = 1 )  

The final answer is the sum of the contributions, which is 4  (3 + 1 = 4)

Query 2 : 
The first prime we consider is 2. 2 divides the first element in our range 1 time, 2 divides the second element 0 times, 2 divides the third element 2 times and 2 divides the fourth element 0 times. Thus 2 contributes a total of 3 to the result ( 1 + 0  + 2 + 0 = 3 ) 
The second prime in our [X, Y] range is 3. 3 divides the first element 0 times, 3 divides the second element 1 time, 3 divides the third element 0 times and 3 divides the fourth element 0 times. Thus 3 contributes a total of 1 ( 0 + 1 + 0 + 0 = 1 )  
The third prime is 5.  5 divides the first element 0 times , 5 divides the second element 0 times, 5 divides the third element 0 times and 5 divides the fourth element 1 time. So 5 contributes 1 ( 0 + 0 + 0 + 1 = 1 )   
The final answer is the sum of all the contributions, which is 5 ( 3 + 1 + 1 = 5)

Note : Use fast I/O due to large input files

Source: codechef | Difficulty: HARD
Tags: Range queries

Segment trees revisited

Number theory

Mathematics

Data structures


Solutions:
from math import sqrt
from bisect import bisect_left, bisect

def sieve():
	n = 10 ** 6 + 1
	spf[1] = 1
	for i in range(2, n):
		spf[i] = i
	for i in range(4, n, 2):
		spf[i] = 2
	for i in range(3, int(sqrt(n - 1)) + 1):
		if spf[i] == i:
			for j in range(i * i, n, i):
				if spf[j] == j:
					spf[j] = i

def pfactorization(n):
	factors = []
	while n != 1:
		factors.append(spf[n])
		n = n // spf[n]
	return factors

def build():
	i = n - 1
	while i > 0:
		tree[i] = sorted(tree[i << 1] + tree[i << 1 | 1])
		i -= 1

def query(l, r, x, y):
	ans = 0
	l += n
	r += n
	while l < r:
		if l & 1:
			forx = bisect_left(tree[l], x)
			fory = bisect(tree[l], y)
			ans += fory - forx
			l += 1
		if r & 1:
			r -= 1
			forx = bisect_left(tree[r], x)
			fory = bisect(tree[r], y)
			ans += fory - forx
		l >>= 1
		r >>= 1
	return ans
spf = [0 for i in range(10 ** 6 + 1)]
sieve()
n = int(input())
array = list(map(int, input().split()))
pf = [pfactorization(array[i]) for i in range(n)]
tree = [0] * 2 * n
for i in range(n):
	tree[i + n] = pf[i]
build()
q = int(input())
for _ in range(q):
	(l, r, x, y) = map(int, input().split())
	print(query(l - 1, r, x, y))


from bisect import bisect, bisect_left
maxn = 10 ** 6 + 100

def sieve_with_spf():
	for i in range(4, maxn, 2):
		spf[i] = 2
	i = 3
	while i * i < maxn:
		if spf[i] == i:
			j = i * i
			while j < maxn:
				if spf[j] == j:
					spf[j] = i
				j += i
		i += 1
N = 10 ** 2 << 1
t = [0] * (N << 1)

def build():
	for i in range(n - 1, 0, -1):
		t[i] = sorted(t[i << 1] + t[i << 1 | 1])

def query(l, r, x, y):
	(res, l, r) = (0, l + n, r + n)
	while l < r:
		if l & 1:
			(res, l) = (res + bisect(t[l], y) - bisect_left(t[l], x), l + 1)
		if r & 1:
			r -= 1
			res += bisect(t[r], y) - bisect_left(t[r], x)
		(l, r) = (l >> 1, r >> 1)
	return res

def getFactorization(n, res):
	while n != 1:
		res.append(spf[n])
		n //= spf[n]
	return res
spf = [i for i in range(maxn)]
sieve_with_spf()
(n, arr) = (int(input()), list(map(int, input().split())))
pF = [getFactorization(arr[i], []) for i in range(n)]
t = [0 for _ in range(n)] + pF + t
build()
for _ in range(int(input())):
	(left, right, x, y) = map(int, input().split())
	print(query(left - 1, right, x, y))


import bisect
b = bisect.bisect
bl = bisect.bisect_left
from sys import stdin, stdout
mx = 10 ** 6 + 1

def soe():
	for i in range(4, mx, 2):
		ar[i] = 2
	for i in range(3, 1001):
		if ar[i] == i:
			for j in range(i ** 2, mx, i):
				if ar[j] == j:
					ar[j] = i
ar = [x for x in range(mx)]
soe()
ar1 = [0] * 400
n = int(stdin.readline())
lz = list(map(int, stdin.readline().split()))
q = int(stdin.readline())
(l1, l3) = ([], [0] * n)
for i in range(n):
	l2 = []
	k = lz[i]
	while k != 1:
		l2.append(ar[k])
		k //= ar[k]
	l1.append(l2)
ar1 = l3 + l1 + ar1
for i in range(n - 1, 0, -1):
	ar1[i] = sorted(ar1[i << 1] + ar1[i << 1 | 1])
for i in range(q):
	(l, r, x, y) = map(int, stdin.readline().split())
	ans = 0
	l += n - 1
	r += n
	while l < r:
		if l & 1:
			ans += b(ar1[l], y) - bl(ar1[l], x)
			l += 1
		if r & 1:
			ans += b(ar1[r - 1], y) - bl(ar1[r - 1], x)
			r -= 1
		l >>= 1
		r >>= 1
	stdout.write(str(ans) + '\n')