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

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

题目描述

求满足 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
1
2

样例解释 1

3 等于 0 的: \{3\}
3 等于 1 的: \{7\}
3 等于 2 的: \{2,5\}

样例输入 2

100000 6

样例输出 2

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