[Softeer][level2] 연탄의 크기 - 파이썬(Python) 풀이

연탄을 모든 집에 배달하려고 했던 산타는 큰 고민에 빠집니다. 각 집에는 연탄 난로가 있는데, 난로와 연탄 모두 원 모양으로 되어있기 때문에 난로의 반지름의 길이가 연탄의 반지름의 길이의 배수인 집에서만 이 연탄을 사용할 수 있다는 것입니다.

 

n개의 집에 각각 놓여 있는 난로의 반지름의 길이가 주어졌을 때, 산타는 연탄의 반지름의 길이를 처음에 잘 설정하여 최대한 많은 집에서 이 연탄을 사용할 수 있도록 만들고자 합니다. 산타를 도와 연탄이 사용가능한 집의 수를 최대로 하는 프로그램을 작성해보세요. 단, 난로의 반지름과 연탄의 반지름은 항상 정수로 나타내지며, 연탄의 반지름은 항상 1보다 커야만 함에 유의합니다.

 

n = int(input())
lst = list(map(int, input().split()))

sosu = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
max_count = 0

for prime in sosu:
    count = sum(1 for num in lst if num % prime == 0)
    if count > max_count:
        max_count = count

print(max_count)