Background

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?……

Problem Description

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.

Input Format

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

Output Format

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

100

50 30

9876543

4938272 3092277

998877665544332211

499438832772166106 312742219398875473

Hint

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

For $100\%$ of the testdata, $1\leq n\leq 10^{18}$.

Translated by ChatGPT 5