欧拉线性素数筛(转)

简介

在埃氏筛中,我们会重复筛到同一个数,例如12同时被2和3筛到,15同时被3和5筛到。所以我们引入欧拉筛,也叫线性筛,可以在$O(n)$的时间内完成对2~n的筛选。它的核心思想是:让每一个最小的合数被其最小质因数筛到


(数论)康托展开和逆康托展开

简介

康托展开是一个全排列到自然数的双射,常用于构建hash表来实现空间压缩。设$n$个数$(1,2,3,4,\cdots n)$,可以组成$n!$种排列,康托展开表示的就是当前的排列在所有组合中的名次。


埃式素数筛

原理

这是最简单的素数筛,一次性打表,效率不是很高,但是比直接判断素数效率高得多。反正开O2冲就完事了。


Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×