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?……
题目描述
给定以下程序中的 $n$（即输入），求以下伪代码的输出结果。
```
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
```
请注意此代码**不是线性筛**，差别在注释过的那一行。
输入格式
无
输出格式
无
说明/提示
**本题采用捆绑测试**，并且存在子任务依赖（只有你拿到了一个子任务前一个子任务的分，你才有可能拿到该子任务的分）。
## 数据范围
| $\text{Subtask}$ | 约束条件 | 分值 |
| :-----------: | :-----------: | :-----------: |
| $1$ | $n\leq 10^7$ |$10$|
| $2$ | $n\leq 10^9$ |$40$|
| $3$ | $n\leq 10^{18}$ |$50$|
对于 $100\%$ 的数据，满足 $1\leq n\leq 10^{18}$。