线性筛小总结

看懂了感觉好有成就感

线性筛的思想应该是每个数只会被筛一遍,因此时间复杂度是线性的(实际全局vis是大于n的,但以每个数的遍历次数来说恰好是1)
设一个合数的来源只有两种:素数 × 素数,或者是 合数 × 最小的素数,这样可以保证每个合数不会重复遍历
如果i为素数,那就令prime[j]小于等于i来避免重复遍历,所以i%prime[j]保证了prime[j]不大于i
如果i为合数,那假如i%prime[j]不为0,那prime[j]就是i×prime[j]分解的最小的素数,否则就意味着i里面含有prime[j],而prime[]表是递增的,后者的i×prime[j+1]所含素数的最小素数肯定不是prime[j+1](prime[j]最小),所以提前break掉

令人惊讶的是一个i%prime[j]就完成了这么繁杂的活

下面是测试用例
观察一下数据,感受感受
15 = 5 × 3
12 = 6 × 2
18 = 9 × 2
45 = 15 × 3
具体程序还是看题解blog吧 ->go

标签: 算法, 学习, 总结

添加新评论