1.质数和合数是针对所有大于1的 “自然数” 来定义的(所有小于等于1的数都不是质数).

2.所有小于等于1的整数既不是质数也不是合数.

3.质数和素数都是同一种性质,只是叫法不同.

4.质数的判定------试除法 或 六倍原理.

(1).”d|n”代表的含义是d能整除n,(这里的”|”代表整除).
(2).一个合数的约数总是成对出现的,如果d|n,那么(n/d)|n,因此我们判断一个数是否为质数的时候,
只需要判断较小的那一个数能否整除n就行了,即只需枚举d<=(n/d),即dd<=n,d<=sqrt(n)就行了.
(3).sqrt(n)这个函数执行的时候比较慢.

5.分解质因数------试除法.(用到的原理:唯一分解定理(算数基本定理))

(1).特别要注意------分解质因数与质因数不一样!!!!!!
(2).分解质因数是一个过程,而质因数是一个数.
(3).一个合数分解而成的质因数最多只包含一个大于sqrt(n)的质因数
(反证法,若n可以被分解成两个大于sqrt(n)的质因数,则这两个质因数相乘的结果大于n,与事实矛盾).
(4).当枚举到某一个数i的时候,n的因子里面已经不包含2-i-1里面的数,
如果n%i==0,则i的因子里面也已经不包含2-i-1里面的数,因此每次枚举的数都是质数.
(5).算数基本定理(唯一分解定理):任何一个大于1的自然数N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积
$$\begin{eqnarray}P & = & p_{1}^{x_{1}}·p_{2}^{x_{2}}·…·p_{m}^{x_{m}}（p_{i}均为质数，x_{i}均为正整数）\end{eqnarray}$$ ，
这样的分解称为 P 的标准分解式。最早证明是由欧几里得给出的，由陈述证明。
此定理可推广至更一般的交换代数和代数数论。
(6).质因子（或质因数）在数论里是指能整除给定正整数的质数。根据算术基本定理，不考虑排列顺序的情况下，
每个正整数都能够以唯一的方式表示成它的质因数的乘积。
(7).两个没有共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。
(8).只有一个质因子的正整数为质数。

6.筛质数.

6.1:朴素筛法.
(1).做法:把2~(n-1)中的所有的数的倍数都标记上,最后没有被标记的数就是质数.
(2).原理:假定有一个数p未被2~(p-1)中的数标记过,那么说明,不存在2~(p-1)中的任何一个数的倍数是p,
也就是说p不是2~(p-1)中的任何数的倍数,也就是说2~(p-1)中不存在p的约数,因此,根据质数的定义可知:
p是质数.
(3).调和级数:当n趋近于正无穷的时候,1/2+1/3+1/4+1/5+…+1/n=lnn+c.(c是欧阳常数,约等于0.577左右.).
(4).底数越大,log数越小
(5).时间复杂度:约为O(nlogn);(注:此处的log数特指以2为底的log数).

6.2:埃氏筛(稍加优化版的筛法).
(1).质数定理:1~n中有n/lnn个质数.
(2).原理:在朴素筛法的过程中只用质数项去筛.
(3).时间复杂度:粗略估计:O(n).实际:O(nlog(logn)).
(4).1~n中,只计算质数项的话,”1/2+1/3+1/4+1/5+…+1/n”的大小约为log(logn).

6.3:线性筛
(1).若n在10的6次方的话,线性筛和埃氏筛的时间效率差不多,若n在10的7次方的话,线性筛会比埃氏筛快了大概一倍.
(2).思考:一:线性筛法为什么是线性的?
二:线性筛法的原理是什么?
(3).核心:1~n内的合数p只会被其最小质因子筛掉.
(4).原理:1~n之内的任何一个合数一定会被筛掉,而且筛的时候只用最小质因子来筛,
然后每一个数都只有一个最小质因子,因此每个数都只会被筛一次,因此线性筛法是线性的.
(5).枚举到i的最小质因子的时候就会停下来,即”if(i%primes[j]==0) break;”.
(6).因为从小到大枚举的所有质数,所以当”i%primes[j]!=0”时,primes[j]一定小于i的最小质因子,
primes[j]一定是primes[j]i的最小质因子.
(7).因为是从小到大枚举的所有质数,所以当”i%primes[j]==0”时,primes[j]一定是i的最小质因子,
而primes[j]又是primes[j]的最小质因子,因此primes[j]是iprimes[j]的最小质因子.
(8).关于for循环的解释:
注:首先要把握住一个重点:我们枚举的时候是从小到大枚举的所有质数
1.当i%primes[j]==0时,因为是从小到大枚举的所有质数,所以primes[j]就是i的最小质因子,而primes[j]又是其本身
primes[j]的最小质因子,因此当i%primes[j]==0时,primes[j]是primes[j]i的最小质因子.
2.当i%primes[j]!=0时,因为是从小到大枚举的所有质数,且此时并没有出现过有质数满足i%primes[j]==0,
因此此时的primes[j]一定小于i的最小质因子,而primes[j]又是其本身primes[j]的最小质因子,
所以当i%primes[j]!=0时,primes[j]也是primes[j]i的最小质因子.
3.综合1,2得知,在内层for循环里面无论何时,primes[j]都是primes[j]i的最小质因子,因此”st[primes[j]i]=true”
语句就是用primes[j]i这个数的最小质因子来筛掉这个数.

【转】对线性筛法的补充理解
首先，线性筛法是对埃氏筛法的优化：因为即使埃氏筛法是朴素做法的优化版，但是还是会重复标记一个合数。
因此，线性筛法的核心步骤，就是避免将一个合数被标记多次，以此达到O(n)O(n)的时间复杂度。体现在代码里面，就是：if (i % primes[j] == 0) break;。

y 总的解释是：primes[j] 一定是 i 的最小质因子。但是这句话并不清晰，或者说由这句话还可以得出一个结论：i 是个合数，并且之前已经被 primes[j] 筛过了。再换个说法，就是说 i 不论乘什么数，都是 primes[j] 的倍数。这就意味着，不需要再使用 i 去筛其他的数，因为 primes[j] 会代劳。
例如：如果 i 是 10，第一个质数是 2，那么 10 % 2 == 0。10 不论乘多少（得到 30, 50, 70, ......），都是第一个质数 2 的倍数，所以没必要用 10 去筛其他数，避免重复标记，因此 break 掉。

但是为什么要把st[primes[j] * i] = true;放在前面？我个人是这么理解的，例如 20，分解质因数为 2 * 2 * 5，但是因为每次只有一个质数和 i 相乘，所以只有在 i == 10 的情况下才能筛掉 20（分解为 2 * 10）。依此类推。

还有一个问题，为什么不用写 j < cnt？因为：

• 如果 i 是质数，那么在循环之前已经被加入到了 primes[] 中，所以一定会存在 i % primes[j] == 0 成立（两个相同的数相除，和为 1，余数为 0），break 掉。
• 如果 i 是合数，一定会存在一个最小质因子，使得 if 语句成立，break 掉；或者在这之前，因为不满足循环条件从而停止循环。

还需注意的是，此处的循环条件primes[j] <= n / i代表的不是primes[j] <= sqrt(n)。取原式的等号，可以得到：primes[j] = n / i，因此可以得到 n = primes[j] * i。也就是说这个条件所代表的是：在 i 已经确定的情况下，primes[j] 为多少才能使得结果小于约束条件 n。因为在这个写法里，要求出的是 1~n 之间的质数。