# Counting numbers in an array that are divisible by any 2 numbers

While solving one question I got stuck with a time limit error. The main objective in question is to count numbers in an array $A$ that are either divisible by $P$, $Q$ or both.

Input format:

The first line contains a single integer $N$ denoting the size of array $A$. The next line contains $N$ space separated integers, where the $i$th integer denotes $A[i]$.

The next line contains a single integer $T$ denoting the number of queries Monk poses to you. Each of the next $T$ lines contains 2 space-separated integers $P$ and $Q$.

Example:

6
2 3 5 7 4 9
2
4 5
3 7


Output:

2
3


The naive approach from my side is this:

a = int(raw_input())                      # Length of an array
b = map(int,raw_input().split())          # Array of size a
c = int(raw_input())                      # Number of query
for _ in xrange(c):
d,e = map(int,raw_input().split())    # 2 numbers
count = 0
for i in b:
if i%d==0:
count+=1
elif i%e==0:
count+=1
print count


I guess it is taking linear time $O(n) + c$ which can be improved to $O(log(n))$ but I am not sure what's the best way to do it or how to implement it.

• Not giving the link to the problem statement at hackerearth deprives readers of a piece of information that might be a giveaway: the category is Integer Factorization & Math Practice Problems. In performance analysis, in may prove necessary to distinguish preparation and queries. Dec 6, 2016 at 19:33