RSA 인수분해 증명

시간 제한2초메모리 제한64 MB

요약

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

난이도: 어려움10점 중 8점
유형: 비트 연산, 그리디, 완전 탐색, 수학
정답자: 아직 제출이 없습니다

문제

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

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

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

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

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

입력

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

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

출력

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

힌트

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

예제3

예제 1
입력
```
2
35
77
```
예상 출력
```
1
```
예제 2
입력
```
3
6
35
77
```
예상 출력
```
2
```
예제 3
입력
```
1
999992936000441063
```
예상 출력
```
1
```