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