1.质因子的定义:每个合数可以写成多个质数相乘的形式,我们称这些质数为该合数的质因子
2.质数的定义:(1)只有1和它本身两个因数的数(2)质因子唯一的数
3.一个合数分解而成的质因子最多只包含一个大于根号n的质因子(如果有两个就爆了
4.朴素质数筛的原理是:质数只有唯一质因子(即它本身
5.虽然都是试除法,但是分解质因子只是个过程,但是质因子都是确切的数字
6.试除法判定质数复杂度是确切的O(√n),但是其实朴素筛法复杂度介于O(nlogn)与O(n√n)之间,例如2的k次
7.埃氏筛法其实说白了就是偷懒,不计入合数的倍数,只计质数的倍数,思想重要,复杂度为O(nloglogn)
8.欧拉筛其实就是更加懒…只用最小质因子来筛,因此每个数只会被筛一次(因为只有一个最小质因子)
9.欧拉筛核心还是算数基本原理,枚举到i的最小质因子时会停下 if (i % primes[j] == 0) break;
10.当 i % primes[j] != 0 时,primes[j]一定小于 i 的最小质因子,所以primes[j] 是 primes[j] * i的最小质因子
11.当 i % primes[j] == 0时,primes[j]一定是 i 的最小质因子,而质数本身也是它本身的最小质因子,仍然有 primes[j] 是 primes[j] * i 的最小质因子
12.质因子(或质因数)在数论里是指能整除给定正整数的质数。根据算术基本定理,不考虑排列顺序的情况下,每个正整数都能够以唯一的方式表示成它的质因数的乘积