P11169 "CMOI R1" Bismuth / Linear Sieve

 > Can you imagine find wakeless,like a satellite,in the black sky? > > Somewhere,like a star. > > We dream about things way beyond this atmosphere. > > At we're now,on the air. > > …… > > But I eventually evaporates in a blackhole… > > Will I just stick up there?……

Given $n$ in the following program (i.e., the input), find the output of the following pseudocode. ``` Input n For i := 1 to n is_not_prime[i] := 0 cntp := 0 counter := 0 For i := 2 to n { If is_not_prime[i] = 0 { cntp := cntp + 1 primes[cntp] := i } For j := 1 to cntp { If i * primes[j] > n break is_not_prime[i * primes[j]] := 1 If i Mod primes[j] > 0 // should be `If i Mod primes[j] = 0` in Sieve of Euler break counter := counter + 1 } } Print cntp, counter ``` Please note that this code is **not a linear sieve**. The difference is the line marked with a comment.

One line with one integer, which is the input, i.e., the given $n$.

One line with two non-negative integers, which are the output of the pseudocode.

**This problem uses bundled tests**, and there are dependent subtasks (only if you get the score of the previous subtask can you possibly get the score of this subtask). # Constraints | $\text{Subtask}$ | Constraints | Score | | :-----------: | :-----------: | :-----------: | | $1$ | $n\leq 10^7$ |$10$| | $2$ | $n\leq 10^9$ |$40$| | $3$ | $n\leq 10^{18}$ |$50$| For $100\%$ of the testdata, $1\leq n\leq 10^{18}$. Translated by ChatGPT 5