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

内存限制:512 MiB 时间限制:2500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

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

输入格式

一行两个整数 n,mn,m

输出格式

输出共 mm 行,每行一个整数,第 ii 行表示 1<pn1<p \leq n 的质数中模 mm 等于 i1i-1 的质数个数。

样例

样例输入 1

7 3

样例输出 1

1
1
2

样例解释 1

33 等于 00 的:{3}\{3\}
33 等于 11 的:{7}\{7\}
33 等于 22 的:{2,5}\{2,5\}

样例输入 2

100000 6

样例输出 2

0
4784
1
1
0
4806

数据范围与提示

对于 25%25\% 的数据,1n1041\leq n\leq 10^4
对于 50%50\% 的数据,1n1071\leq n\leq 10^7
对于 75%75\% 的数据,1n1091\leq n\leq 10^9
对于 100%100\% 的数据,1n3×1010,1<m12,n>m1\leq n\leq 3\times 10^{10},1<m \leq 12,n>m