Hackerearth: Counting numbers in an array that are divisible by any 2 numbers

Always assume that coding challenge websites will give you worst case scenarios to test your code. They won't test your code with small arrays of small numbers. They'll give you large arrays with huge numbers that will expose things like O(n²) algorithms.

Your challenge is not to write the naive solution, but to figure out how to reduce this complexity.

Also, you want to separate the getting of the data from the processing of it.

When it comes down to factorizing the numbers, we only have to determine the factors of a number once. If my input was 16 32 64 I'd only have to figure out that the factors of 16 are 1, 2, 4, 8, 16 once, and then when, in the process of calculating the factors of 32 I calculated the factors of 16, I'd already know that and just need to add 32 to that set. We can achieve this by memoizing. A dictionary mapping integers to sets of factors seems a reasonable approach to that.

If we were to use modern Python 3, a straightforward approach to memoizing this might look like the following. If we create an instance of FactorGenerator as fg every time we call fg.factor we'll take advantage of every previously call to reduce the work being done.

import math

class FactorGenerator(object):
    def __init__(self):
        self.memo = {1: {1}, 2: {1, 2}, 3: {1, 3}}
    
    def factor(self, n):
        if factors := self.memo.get(n):
            return factors
        
        self.memo[n] = {1, n}
        
        for div in range(2, int(round(math.sqrt(n))) + 1):
            if n % div == 0:
                self.memo[n] |= {div} | self.factor(n // div)
        
        return self.memo[n]

Now you'd simply call this on every element in the input array and for your sample you'd end up with fg.memo being:

{1: {1}, 2: {1, 2}, 3: {1, 3}, 5: {1, 5}, 
 7: {1, 7}, 4: {1, 2, 4}, 9: {1, 3, 9}}

Now we convert the list of numbers to check for to a set, and we can just loop over the input numbers, and check to see if their corresponding entry in that memo, intersected with the set to look for, is an empty set or not.

Leveraging this to solve this problem might look like:

import math

class FactorGenerator(object):
    def __init__(self):
        self.memo = {1: {1}, 2: {1, 2}, 3: {1, 3}}
    
    def factor(self, n):
        if factors := self.memo.get(n):
            return factors
        
        self.memo[n] = {1, n}
        
        for div in range(2, int(round(math.sqrt(n))) + 1):
            if n % div == 0:
                self.memo[n] |= {div} | self.factor(n // div)
        
        return self.memo[n]

def main():
    n_integers = int(input())
    integers = list(map(int, input().split()[:n_integers]))
    num_sets_to_check = int(input())
    sets_to_check = [
        set(map(int, input().split()[:2]))
        for _ in range(num_sets_to_check)
    ]
    fg = FactorGenerator()

    for s in sets_to_check:
        c = 0
        for i in integers:
            if s & fg.factor(i):
                c += 1
        print(c)
    
if __name__ == '__main__':
    main()

Portability

I realize this question was posted many years ago when Python version 2.x was prevalent, but now that it is deprecated, consider porting to 3.x. To do so, it is necessary to add parentheses for print calls. Change:

print count

to:

print(count)

Also, change raw_input to input and xrange to range.

UX

When I run the code, it sits there waiting for me to input something, but I don't know what is expected. Perhaps the website you are using prohibits displaying text prompts, but since this is a code review, you should always prompt the user with helpful text, such as:

a = int(input("How many integers in your set? "))

DRY

This line is repeated in both branches of the if/elif statement:

count+=1

You can eliminate the elif and the repetition:

if (i%d==0) or (i%e==0):
    count+=1

Layout

There is inconsistent use of whitespace around operators. For example,

count+=1

would be better written as:

count += 1

The black program can be used to automatically format the code with consistent whitespace.

Naming

Many of the variable names are not very meaningful. Arrays are usually pluralized. Instead of b, consider using integers. a would be better as num_of_ints, etc.

Documentation

The PEP 8 style guide recommends adding a docstring at the top of the code to summarize its purpose.

"""
Descrbe the problem here
"""