[AdditionalFile6028.zip](file://AdditionalFile6028.zip?type=additional_file)

#6028. 「from CommonAnts」质数计数 II

标签: 传统 | 时间限制: 2500 ms | 内存限制: 512 MiB |

题目描述

求满足 $1<p \leq n$ 的质数中，模 $m$ 等于 $0,1,2,...,m-1$ 的分别有多少个。

输入格式

一行两个整数 $n,m$。

输出格式

输出共 $m$ 行，每行一个整数，第 $i$ 行表示 $1<p \leq n$ 的质数中模 $m$ 等于 $i-1$ 的质数个数。

样例 1

输入

7 3

输出

1
1
2

模 $3$ 等于 $0$ 的：$\{3\}$； 模 $3$ 等于 $1$ 的：$\{7\}$； 模 $3$ 等于 $2$ 的：$\{2,5\}$。

样例 2

输入

100000 6

输出

0
4784
1
1
0
4806

数据范围与提示

对于 $25\%$ 的数据，$1\leq n\leq 10^4$；
对于 $50\%$ 的数据，$1\leq n\leq 10^7$；
对于 $75\%$ 的数据，$1\leq n\leq 10^9$；
对于 $100\%$ 的数据，$1\leq n\leq 3\times 10^{10},1<m \leq 12,n>m$。