from collections import defaultdict
 
def factorize(n):
    factors = defaultdict(int)
    while n % 2 == 0:
        factors[2] += 1
        n //= 2
    for i in range(3, int(n**0.5) + 1, 2):
        while n % i == 0:
            factors[i] += 1
            n //= i
    if n > 2:
        factors[n] += 1
    return factors
 
def max_divisible_elements(arr, k):
    prime_factors_count = defaultdict(int)
    for num in arr:
        factors = factorize(num)
        for factor, count in factors.items():
            prime_factors_count[factor] += count
 
    max_divisible = 0
    for factor, count in prime_factors_count.items():
        max_divisible = max(max_divisible, count // k)
 
    return max_divisible
 
# Example usage:
arr = [1,2,3,4,5,6]
k = 6
print(max_divisible_elements(arr, k))  # Output: 3

ZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgZGVmYXVsdGRpY3QKCmRlZiBmYWN0b3JpemUobik6CiAgICBmYWN0b3JzID0gZGVmYXVsdGRpY3QoaW50KQogICAgd2hpbGUgbiAlIDIgPT0gMDoKICAgICAgICBmYWN0b3JzWzJdICs9IDEKICAgICAgICBuIC8vPSAyCiAgICBmb3IgaSBpbiByYW5nZSgzLCBpbnQobioqMC41KSArIDEsIDIpOgogICAgICAgIHdoaWxlIG4gJSBpID09IDA6CiAgICAgICAgICAgIGZhY3RvcnNbaV0gKz0gMQogICAgICAgICAgICBuIC8vPSBpCiAgICBpZiBuID4gMjoKICAgICAgICBmYWN0b3JzW25dICs9IDEKICAgIHJldHVybiBmYWN0b3JzCgpkZWYgbWF4X2RpdmlzaWJsZV9lbGVtZW50cyhhcnIsIGspOgogICAgcHJpbWVfZmFjdG9yc19jb3VudCA9IGRlZmF1bHRkaWN0KGludCkKICAgIGZvciBudW0gaW4gYXJyOgogICAgICAgIGZhY3RvcnMgPSBmYWN0b3JpemUobnVtKQogICAgICAgIGZvciBmYWN0b3IsIGNvdW50IGluIGZhY3RvcnMuaXRlbXMoKToKICAgICAgICAgICAgcHJpbWVfZmFjdG9yc19jb3VudFtmYWN0b3JdICs9IGNvdW50CiAgICAKICAgIG1heF9kaXZpc2libGUgPSAwCiAgICBmb3IgZmFjdG9yLCBjb3VudCBpbiBwcmltZV9mYWN0b3JzX2NvdW50Lml0ZW1zKCk6CiAgICAgICAgbWF4X2RpdmlzaWJsZSA9IG1heChtYXhfZGl2aXNpYmxlLCBjb3VudCAvLyBrKQogICAgCiAgICByZXR1cm4gbWF4X2RpdmlzaWJsZQoKIyBFeGFtcGxlIHVzYWdlOgphcnIgPSBbMSwyLDMsNCw1LDZdCmsgPSA2CnByaW50KG1heF9kaXZpc2libGVfZWxlbWVudHMoYXJyLCBrKSkgICMgT3V0cHV0OiAz