在门户网站中营销者通过制作什么,漫画网站做任务给金币,批量做网站引流,express wordpress质数筛选法 1.暴力筛选法 :smirk:2.普通优化 :rofl:3.埃氏筛法:cold_sweat:4.线性筛选法:scream: 质数#xff1a;除了1和他本身没有其它因数的正整数就是质数。1不是质数#xff0c;2是质数。 1.暴力筛选法 #x1f60f;
原理 求x的质数#xff0c;令y从2到 x \sqrt[]{x… 质数筛选法 1.暴力筛选法 :smirk:2.普通优化 :rofl:3.埃氏筛法:cold_sweat:4.线性筛选法:scream: 质数除了1和他本身没有其它因数的正整数就是质数。1不是质数2是质数。 1.暴力筛选法
原理 求x的质数令y从2到 x \sqrt[]{x} x 向下取整比如2.42依次尝试 如果x%y0那么x不是质数。2要单独讨论否则按照这个逻辑2不是质数。 为什么取 x \sqrt[]{x} x ? 答如果取到 x \sqrt[]{x} x 还没有找到x的约数那么就可以断定x一定是质数。 x \sqrt[]{x} x * x \sqrt[]{x} x x这是一个特殊的位置。可以将这个等式抽象为a * bx。a和b的关系是你消我涨即a x b {x \over b} bx。 x \sqrt[]{x} x 是ab的特殊情况如果a小于等于 x \sqrt[]{x} x 的数里没有x的约数那么当a大于 x \sqrt[]{x} x 的时候一样没有因为a小于等于 x \sqrt[]{x} x 的时候b是大于等于 x \sqrt[]{x} x 的。排除a不是x的约数的同时将b也排除了因为约数是成对出现的。所以当a大于 x \sqrt[]{x} x 的时候实际上在做重复的计算相当于把ab交换了一个位置实际上当a取值小于等于 x \sqrt[]{x} x 的时候已经把所有可能的约数排除了。为什么 x \sqrt[]{x} x 要向下取整而不是向上取整 答第一个问题解释了约数是成对出现的只需要枚举a从2到 x \sqrt[]{x} x 即可那么b x a {x \over a} ax同时被考虑到了。如果 x \sqrt[]{x} x 不是整数那么就向下取整去掉小数部分这样可以保证a的枚举没有遗漏a小于等于 x \sqrt[]{x} x 。如果向上取整那么a的取值大于 x \sqrt[]{x} x b小于 x \sqrt[]{x} x 。这个组合实际上之前可能已经被排除了所以重复计算了一对约数。可能会遗漏约数导致判断错误。为什么2要单独考虑? 答代码的逻辑是从2到 x \sqrt[]{x} x 依次找x的约数但是2本身可以被2整除这样就会误判2有约数所以2要特判一下。 代码
#includeiostream
#includecmath
using namespace std;bool violence(int n) //violence 暴力
{if (n 1)return false;if (n 2)return true;for (int i 2; i sqrt(n); i) //sqrt函数向下取整的{if (n % i 0)return false; //可以被i整除不是质数}return true;
}int main()
{for (int i 1; i 100; i) // 找到1-100内的质数{if (violence(i))cout i ;}return 0;
}运行结果
2.普通优化
优化原理 先贴上代码好理解否则讲半天不知道在说什么。看完回到这里如果看懂了跳过否则看下一行唯一的难点为什么当 st[i] false则 i 一定是质数呢 答当遍历到 i 的时候2~i-1的所有倍数都被标记成合数了如果此时i没有被标记说明i一定是质数。因为i的约数一定是在[2,i-1]的区间内的而这个区间的所有数的倍数都不能构成i说明这些数都不是i的约数那么i就是质数。
int primes[N], cnt; // primes[]存储所有质数cnt记录质数的下标
bool st[N]; // st[i]true表示i不是质数void get_prime(int n) //挑选2到n中所有的质数
{for(int i 2; i n; i ){if(!st[i]) //当前的数是i如果st[i]false那么说明i这个数一定是质数(理解不了先不解释看后面的代码)primes[cnt ] i; //存储当前的质数for(int j i i; j n; j i) //将i的所有倍数都标记为true因为i的倍数一定不是质数。st[j] true; }
}3.埃氏筛法 数的公理( 两种形式 ( 1 ) 任意一个正整数大于等于 2 x 1 k 1 ∗ x 2 k 2 ∗ . . . . ∗ x n k n (1)任意一个正整数大于等于2x_1^{k_1}*x_2^{k_2}*....*x_n^{k_n} (1)任意一个正整数大于等于2x1k1∗x2k2∗....∗xnkn ( 2 ) 任意一个正整数大于等于 2 x 1 k 1 ∗ ( x 2 k 2 ∗ . . . . ∗ x n k n ) (2)任意一个正整数大于等于2x_1^{k_1}*(x_2^{k_2}*....*x_n^{k_n}) (2)任意一个正整数大于等于2x1k1∗(x2k2∗....∗xnkn) 其中 x n x_n xn都是质因数 k n k_n kn是大于等于0的正整数 用人话说就是一个数分解开来一定是若干个质数相乘这些分开的数一定是质数如果发现分解的数有合数那么就没有分解彻底再把合数分解成质数 优化原理 普通优化是将 i 之前的所有数的倍数都标记以此判断i是不是合数。但是数的公理第2个形式说明了一个数必然是由若干个质数的乘积构成的那么就不需要取将i之前所有数的倍数标记只需要将i之前的所有质数的乘积标记就可以了。
int primes[N], cnt; // primes[]存储所有质数cnt记录质数的下标
bool st[N]; // st[i]true表示i不是质数void get_primes(int n)//挑选2到n中所有的质数
{for (int i 2; i n; i ){if (st[i]) //如果st[i]true,说明i不是质数continue; primes[cnt ] i;for (int j i i; j n; j i) //只要把质数的倍数筛选掉就可以了。st[j] true;}
}4.线性筛选法 前集回顾 埃式筛选法有一个很明显的缺陷即筛选标记合数的时候有大量重复的步骤。比如 当 i 3的时候将6951都标记了。当 i 17 的时候会标记3451发现有重复的项51。 目的和公理 目的 让每个合数只会被筛选一次。数学公理 每个数都有一个最小质因数比如2的最小质因数是24的最小质因数是25的最小质因数是56的最小质因数是27的是78的是29的是310的是211的是1112的是2… 原理 任何数只有一个最小质因数只要保证每个合数都是最小质因数筛选的就可以保证不会重复筛选。有点难以理解
int primes[N], cnt; // primes[]存储所有质数cnt记录质数的下标
bool st[N]; // st[i]true表示i不是质数void get_primes(int n)
{for (int i 2; i n; i ){if (!st[i]) primes[cnt ] i; //合理性证明最底下for (int j 0; primes[j] n/i; j ){st[primes[j] * i] true; //筛选的合数primes[j] * i的最小质因数一定是primes[j],就用primes[j]去筛选它if (i % primes[j] 0) //为了避免重复筛选合数。//如果i % primes[j] 0则primes[j]是i的最小质因数同时说明primes[j]是i*primes[j]的最小质因数因为primes[j]是递增的//如果继续循环下一步就是st[primes[j1]*i]true,因为primes[j1]primes[j],primes[j1]i,所以primes[j1]*i的最小质因数仍然是primes[j],//但是根据原理一个数需要被他的最小质因数筛选才不会重复这里却用primes[j1]筛选了primes[j1]*i。重复筛选了。break;}}
}
i筛掉的数2436,948510,15,25612714,21,35,49816919,2710201122,33,55,77,121
Question区
1.为什么st[i]false可以表示是质数明明下面的for循环和埃式筛选法不一样 答i x 1 x_1 x1* x 2 x_2 x2 x 1 x_1 x1表示x的最小质因数 x 1 x_1 x1是[2,i-1]里面的一个质数 x 2 x_2 x2可以是质数也可以是合数。1 x 2 x_2 x2是质数我们从代码可以归纳出当k2~i-1是质数的时候它会筛掉所有的k * primes[j]j从0到cnt-1, 所以i会被[2,i-1]内的某一个质数筛掉。2 x 2 x_2 x2是合数我们从代码归纳出当k是合数的时候会筛选出[2,k的最小质因子] * primes[j] 而 x 1 x_1 x1是最小质因数那么一定有一个k会筛选出 x 2 x_2 x2. 2.为什么要if (i % primes[j] 0)break 答按照原理来的每个数都要由他的最小质因数来更新如果说这一步不退出而是继续循环那么下一步i * primes[j1]将被筛选掉但是i * primes[j1]的最小质因数是primes[j]因为i不变上一步i%primes[j]0且primes[j1]primes[j])而现在i * primes[j1]由primes[j1]来筛选了这样导致筛选过程提前了后面又会筛选导致重复当i变大的时候会再次筛选一次。
线性筛选法还是很难理解的。本质在于每个数只被筛选一次且是被去最小质因数筛选的。
