博主是个数学菜鸡，它考试几乎没及格过，但是他牛逼的同学们要他写笔记，so,他只能硬着头皮屑了，咕咕咕，可能有很多错误还望海涵!

有关素数的小结

质数(prime number)又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数。来自360百科

证明素数无限多

先来个简单的：

2是素数,23是素数,233是素数,2333是素数,23333是素数,233333是素数,2333333是素数,23333333是素数,233333333是素数........

其实以上是放屁....

正确的证明:

经典反证法：

假设素数是有限的,假设素数只有有限的\(n\)个,最大的一个素数是p
设q为所有素数之积加上1,那么,\(q = （ 2 * 3 * 5 * …… * p ）+ 1\)不是素数
那么,q可以被\(2、3、……p\)中的数整除
而q被这\(2、3、……、p\)中任意一个整除都会余1,与之矛盾
所以,素数是无限的.

####素数计数函数：

好想没什么用，看看就行了...咕咕咕

小于或等于 \(x\) 的素数的个数，用 \(\pi(x)\) 表示。随着 \(x\) 的增大，有这样的近似结果： \(\pi(x) \sim \frac{x}{\ln(x)}\)

素数判定

暴力做法

自然可以枚举从小到大的每个数看是否能整除

bool Prime(int x) {
  if (x < 2) return 0;
  for (int i = 2; i < x; ++i)
        if (x % i == 0) 
                return 0;
  return 1;
}

小优化

只需要循环到\sqrt{a}

数论学习笔记

原文：https://www.cnblogs.com/pyyyyyy/p/10882892.html