北京网站备案拍照地址鼓楼,wordpress支付宝扫码支付宝,网站开发的进度怎么写,网站建设 万网 域名原理
线性筛是一种可以在线性时间内将素数筛选出来的算法#xff0c;其中的主要思想在于保证合数只会被它的最小质因数筛掉并且筛掉一次。
代码
下面是线性筛的算法CPP实现#xff1a;
vectorint generate_primes_linear_time(int n) {vectorint lp(n 1…原理
线性筛是一种可以在线性时间内将素数筛选出来的算法其中的主要思想在于保证合数只会被它的最小质因数筛掉并且筛掉一次。
代码
下面是线性筛的算法CPP实现
vectorint generate_primes_linear_time(int n) {vectorint lp(n 1);vectorint primes;for (int i 2; i n; i) {if (lp[i] 0) {lp[i] i;primes.push_back(i);}for (int j 0; j primes.size() primes[j] lp[i] i * primes[j] n; j)lp[i * primes[j]] primes[j];}return primes;
}其中 l p [ i ] lp[i] lp[i]保存了 i i i的最小质因数 p r i m e s primes primes则是存储了从小到大的质数。
简单证明
所有的合数只会被筛掉一次
假设存在一个合数被筛掉了两次即存在合数 C i ∗ p i p j ∗ j ( p i p j ) Ci*p_ip_j*j(p_ip_j) Ci∗pipj∗j(pipj)那么就可以得出它被两个不同的质数 p i , p j p_i,p_j pi,pj筛过两次那么很容易得到 p j ∣ i p_j | \ i pj∣ i并且有 p i p j p_i p_j pipj那么表明此时对于倍数 i i i的时候在枚举到质数 p j p_j pj就会退出循环而不会枚举到 p i p_i pi因此假设不成立。可以保证所有的合数有且并被筛过一次。
下一个没有被筛掉的数字一定是素数
假设下一个没有被筛掉的数字为 x x x那么我们假设它不是素数则有 x p x ∗ q ( p x x , q x ) xp_x*q(p_x x, q x) xpx∗q(pxx,qx)其中 p x p_x px是 x x x的最小质因数那么对于倍数 q q q在枚举素数的时候没有枚举到 p x p_x px表明存在更加小的素数 p y p_y py使得 p y ∣ q p_y | \ q py∣ q因此也有 p y ∣ x p_y | \ x py∣ x所以 p x p_x px并不是 x x x的最小质因数。假设不成立所以 x x x是素数。
