안티소수

시간 제한3초메모리 제한512 MB

요약

n이 주어질 때 n 이하에서 가장 큰 고합성수를 찾는다. 즉, 자기보다 작은 모든 양의 정수보다 약수가 많은 수 중 n을 넘지 않는 최대값을 구한다.

난이도: 보통10점 중 6점
유형: 정수론, 완전 탐색, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

어떤 양의 정수가 자기 자신보다 작은 모든 양의 정수보다 약수의 개수가 더 많을 때, 그 수를 안티소수(antiprime), 또는 고도 합성수(highly composite number)라고 부른다. 예를 들어 $1, 2, 4, 6, 12, 24$ 는 모두 안티소수이다.

정수 $n$ 이 주어질 때, $n$ 보다 크지 않은 안티소수 중 가장 큰 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 $n$ 이 주어진다. ( $1 \le n \le 2000000000$ )

출력

$n$ 보다 크지 않은 안티소수 중 가장 큰 값을 한 줄에 출력한다.

예제4

예제 1
입력
```
1000
```
예상 출력
```
840
```
예제 2
입력
```
1
```
예상 출력
```
1
```
예제 3
입력
```
2
```
예상 출력
```
2
```
예제 4
입력
```
3
```
예상 출력
```
2
```