听话小甜瓜

文章
5
资源
0
加入时间
2年10月21天

质数线性筛

其实基本的素数筛,时间复杂度也能到达O(n*loglogn),线性筛的提速并不是很明显,但这种思想还是值得学习的,这一版本是基于合数都可拆解为几个质因数相乘,只用用最小质因数筛一遍实现O(n)的复杂度。void as(int n){ REW(a,0);//0代表是素数。 a[0]=a[1]=1; t=0; FOR(i,2,n) { i...