Python | Cuente los elementos de la array con factores menores o iguales a los factores de x dada

Dada una array, la tarea es contar los elementos de la array cuyos factores son menores que el número x dado . Ejemplos:

Entrada: arr = [2, 12, 4, 6], x = 6 Salida: 2 factores de x = 6 es [1, 2, 3] factores de arr[0] = 2 es [1] factores de arr[1 ] = 12 es [1, 2, 3, 4] factores de arr[2] = 4 es [1, 2] factores de arr[3] = 6 es [1, 2, 3] entonces solo arr[0] y arr[2] son ​​la respuesta.

Enfoque: Averigüe los factores de todos los elementos y el de x dado y luego compárelos todos si los factores de los elementos son menores que los factores de x, luego incremente la cuenta. A continuación se muestra la implementación del problema anterior: 

from math import ceil, sqrt
  
# function to count the factors of an array
def factorscount(x):
    count = 0
    for i in range(1,ceil(sqrt(x))):
        if x%i==i:
            count+=1
        else:
            count+=2
    return count
  
def Totalcount(arr, x):
     
    # count of factors of  given x
    count_fac = factorscount(x)
     
    # store the count of each factors
    arr_fac = [factorscount(i) for i in arr]
  
    ans = 0
  
    for i in arr_fac:
        # if factors count of element of array is
        #small than that of given number
        if i<count_fac:
            ans+=1
  
    return ans
  
  
# Driver code
  
arr = [2,12,4,6]
x = 6
print(Totalcount(arr, x))

2

Complejidad de tiempo: O(√x+n√k) donde n es el tamaño de la array, x es el número dado y k es el elemento máximo en la array.
Espacio Auxiliar: O(n)