The Romanian Sieve
시간 제한2초메모리 제한2048 MB
시간 예산 t가 주어질 때, 약수 순회 이중 루프가 t번 이하로 실행되는 가장 큰 n을 구한다.
문제
Ionuț Cercel (the son of Petrică Cercel) achieved everything there was to achieve in music after the absolute hit "Made in Romania".
Now he got an interest in competitive programming. In his preparation for the training camp in Phapos, he came across a concept called "The Romanian Sieve", which can be summarized by the following piece of code:
int64_t iters = 0;
for (int64_t i = 1; i ≤ n; i++) {
for (int64_t j = i; j ≤ n; j += i) {
max_div[j] = i;
iters++;
}
}
As a curious individual, Ionuț asks himself: "Given an integer , what is the largest value of such that iters after running the Romanian Sieve algorithm?" Please help him answer this question.
입력
The first line contains an integer ().
출력
Print one integer: the maximum such that iters after running the algorithm.