Modified Sieve Counting

Given a positive integer \(n\), simulate the following pseudo-code and output the results. The pseudo-code processes numbers from 2 to \(n\) and maintains two variables:

• \(cntp\): the number of numbers that are not marked (i.e. they are considered prime in this algorithm).
• \(counter\): a counter increased only in a specific condition while processing multiples.

The algorithm is a modified sieve. Note that the inner loop contains a condition: \[ i \bmod primes[j] > 0? \quad \text{if true, break the loop (instead of continuing as in Euler's sieve)}. \]

The pseudo-code is given below:

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
            break
        counter := counter + 1
    }
}
Print cntp, counter

Your task is to simulate this algorithm and output the final values of cntp and counter separated by a space.

inputFormat

Input consists of a single line containing one integer \(n\) (\(n \ge 2\)).

outputFormat

Output two integers: the first is cntp (the number of primes found by the algorithm) and the second is counter (the number of times a certain multiplication condition was met), separated by a space.

sample

2

1 0