The Romanian Sieve

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

요약
시간 예산 t가 주어질 때, 약수 순회 이중 루프가 t번 이하로 실행되는 가장 큰 n을 구한다.
난이도

보통10점 중 6점

유형
수학, 이분 탐색, 정수론
정답자
아직 제출이 없습니다

문제

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 tt, what is the largest value of nn such that iters ≤t\leq t after running the Romanian Sieve algorithm?" Please help him answer this question.

입력

The first line contains an integer tt (1≤t≤3⋅10131 \leq t \leq 3 \cdot 10^{13}).

출력

Print one integer: the maximum nn such that iters ≤t\leq t after running the algorithm.

예제2

  1. 예제 1

    입력
    11
    
    예상 출력
    5
    
  2. 예제 2

    입력
    2846010382
    
    예상 출력
    149946143