문제
N개의 자연수들이 주어진다. 당신은 이 수들 중 두 수를 골라서 아래와 같은 작업을 할 수 있다.
작업) 두 수 A, B를 고른 후 A의 소인수 p를 선택해서, A와 B를 지우고 A/p와 B×p를 넣는다.
몇 번의 작업을 해서 N개의 수들의 최대공약수가 최대가 되게 할 때,
그 최댓값을 구하고 최소 몇 번의 작업을 해야 하는지 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 N이 주어진다. (1 ≤ N ≤ 100) 두 번째 줄에는 처음에 주어진 N개의 자연수들이 주어진다. 이 수들은 1,000,000 이하이다.
출력
최대공약수로 가능한 최댓값과 그 때 필요한 최소 작업 수를 출력한다.
예제1
입력
3
441
출력
21 예제2
입력
3
8249
출력
123 예제3
입력
5
45678
출력
22 힌트
출처
COCI 2009/2010 contest 4 task 3 Iks