팩토리얼 곱에서 잘라내기

면접 대비

시간 제한1초메모리 제한128 MB

요약

2 이상 500 이하의 k가 주어질 때, 1!, 2!, ..., k! 중 일부를 제거해 남은 곱이 완전제곱수가 되도록 하는 최소 제거 개수를 구한다.

난이도: 보통10점 중 6점
유형: 수학, 정수론, 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

양의 정수 $n$ 의 팩토리얼 $n!$ 은 $1$ 부터 $n$ 까지의 모든 정수의 곱입니다. 즉 $n! = 1 \times 2 \times 3 \times \cdots \times n$ 입니다.

처음 $k$ 개의 팩토리얼의 곱 $1! \times 2! \times 3! \times \cdots \times k!$ 을 생각합니다. 이 곱에서 팩토리얼 몇 개를 통째로 골라 곱셈에서 제외할 수 있습니다. 남은 팩토리얼들의 곱이 어떤 정수의 완전제곱수(제곱수)가 되도록 만들려고 합니다.

이때 제외해야 하는 팩토리얼의 최소 개수를 구하세요.

입력

정수 $k$ 가 한 줄에 주어집니다. ( $2 \le k \le 500$ )

출력

남은 팩토리얼들의 곱이 완전제곱수가 되도록 하기 위해 제외해야 하는 팩토리얼의 최소 개수를 한 줄에 출력합니다.

예제4

예제 1
입력
```
4
```
예상 출력
```
1
```
예제 2
입력
```
6
```
예상 출력
```
2
```
예제 3
입력
```
2
```
예상 출력
```
1
```
예제 4
입력
```
7
```
예상 출력
```
3
```