cho.sh

RSA 인수분해 증명

최대 36개의 소수로 이루어진 10만 개 이하의 모듈러스가 주어질 때, 각 모듈러스에서 그 소수들을 나눠 남은 값이 1이나 소수가 되도록 하는 최소 소수 집합의 크기를 구한다.

어려움8비트 연산그리디완전 탐색수학아직 제출이 없습니다시간 제한2초메모리 제한64 MB

문제

미르코가 암호학에 흥미를 느껴 Multiprime RSA 알고리즘을 바탕으로 공개 키 시스템을 만들기 시작했다. 시스템의 세부 사항은 이 문제와 상관없다. 중요한 것은 모든 키에 모듈러스가 들어간다는 점이다. 모듈러스는 서로 다른 두 개 이상의 소수를 곱한 자연수다. 시스템이 안전하려면 모듈러스를 보통의 시간 안에 소인수분해하기 어려워야 한다. 이 조건은 필요조건이지만 충분조건은 아닐 수도 있다.

미르코는 경험이 부족해서 첫 단계인 무작위 소수 생성부터 실수했다. 생성기의 엔트로피가 모자라서 서로 다른 소수를 모두 합쳐 36개까지만 만들 수 있고, 만들어지는 소수는 모두 10910^9보다 작다. 따라서 미르코가 얻는 모듈러스는 전부 이 36개 소수 중 몇 개를 곱한 값이다.

미르코는 서로 다른 모듈러스 NN개를 만든 뒤, 친구 슬라브코에게 모든 모듈러스를 끝까지 소인수분해해 달라고 부탁하며 안전성 시험을 맡겼다. 미르코 생성기의 한계를 아는 슬라브코는 모든 모듈러스를 완전히 분해하고, 그 결과를 되도록 효율적으로 알려주려 한다.

슬라브코는 답으로 인수분해 증명을 보낸다. 인수분해 증명은 소수의 집합이며, 각 모듈러스를 그 집합에 속하면서 자신을 나누는 소수 전부로 나누면 결과가 1이거나 소수 하나가 되는 성질을 만족한다. 미르코는 인수분해를 알고 있으므로, 증명을 받으면 슬라브코가 정말로 모든 모듈러스를 끝까지 분해했는지 쉽게 확인할 수 있다.

서로 다른 모듈러스 NN개가 주어질 때 가장 작은 인수분해 증명의 크기를 구하는 프로그램을 작성하라. 증명에 들어가는 소수를 직접 찾을 필요는 없다. 최소 몇 개가 필요한지만 구하면 된다.

입력

첫째 줄에 미르코가 슬라브코에게 낸 문제에 들어 있는 모듈러스의 개수 NN이 주어진다 (1≤N≤100 0001 \le N \le 100\,000). 다음 NN개 줄에는 미르코가 슬라브코에게 보내는 모듈러스 XiX_i가 한 줄에 하나씩 주어진다 (2≤Xi≤10182 \le X_i \le 10^{18}).

각 XiX_i는 10910^9보다 작은 서로 다른 두 개 이상의 소수를 곱한 값이다. 인수로 등장하는 소수의 총 개수는 36개를 넘지 않는다.

출력

첫째 줄에 가장 작은 인수분해 증명의 크기를 출력한다.

힌트

첫 번째 예제에서 35=5×735 = 5 \times 7이고 77=7×1177 = 7 \times 11이다. 인수분해 증명으로는 소수 하나, 즉 77만 있으면 충분하다. 77로 나누면 두 모듈러스는 55와 1111이 되고 둘 다 소수다.