定义：

若一个正整数无法被除了1和它自身之外的任何自然数整除，则称该数为质数(或素数)，否则称该正整数是合数。

浅谈： 

在整个自然数集合中，质数的数量不多，分布比较稀疏，对于一个足够大的整数N，不超过N的质数大约有 N / lnN 个，即每 lnN 个数中大约有一个质数.

质数的判定： 

试除法：

        若一个正整数N为合数，则存在一个能整除N的数T，其中2<=T<= sqrt(N).

证明：

        由定义得，因为N是合数，所以存在一个能整除N的数M，其中2 <= M <= N - 1.

反证法：

        假设命题不成立，那么这样的数M一定满足 sqrt(N) + 1 <= M <= N - 1，因为M能整除N，所以它们的商N / M也能整除N。而2 <= N / M <= sqrt(N)，令 T = N / M，这与假设矛盾，故假设不成立，原命题成立。证毕.

根据上述命题，我们只需要扫描 2 ~ sqrt(N) 之间的所有整数，依次检查它们能否整除N，若都不能整除，则N是质数，否则，N是合数。试除法的时间复杂度为O(sqrt(N))。当然，我们需要特判0和1两个整数，它们既不是质数，也不是合数。

bool isprime(int n) {if (n == 0 || n == 1) {return false;}for (int i = 2; i * i <= n; i++) {if (n % i == 0) {return false;}}return true;
}

"试除法"作为最简单也最经典的确定性算法，是我们在算法竞赛中通常会使用的方法。我们可以从以下两点对其进行优化：

         <1>.2，3，5是最小的3个质数，我们可以特判这三个数。

         <2>.2，3，5是最小的3个质数，因此很多合数都以这三个数为因子，所以对于2，3，5的倍数，我们首先要排除掉。

bool isprime(int n) {if (n == 0 || n == 1) {return false;}if (n == 2 || n == 3 || n == 5) {return true;}if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) {return false;}for (int i = 2; i * i <= n; i++) {if (n % i == 0) {return false;}}return true;
}

质数的筛选：

给定一个整数N，求出1 ~ N之间的所有质数，成为质数的筛选问题。

Eratosthenes筛法：

        对于整数x的倍数 2x，3x，4x，......，都不是质数。根据质数的定义，上述命题显然成立。

        我们可以从2开始，由小到大扫描每一个数x，把它的倍数标记为合数。当扫描到一个数时，若它尚未被标记，则它不能被2 ~ x - 1之间的任何数整除，该数就是质数。另外，我们可以发现，2和3都会把6标记为合数。实际上，小于x^2的x的倍数在扫描更小的数时，就已经被标记过了。因此我们可以对Eratosthenes筛法进行优化，对于每一个数字x，我们只需要从x^2开始，把x^2，(x + 1) * x， ......标记为合数即可。

void Getprimes(int n) {std::memset(v, 0, sizeof v); //合数标记for (int i = 2; i <= n; i++) {if (v[i]) {continue;}std::cout << i << "\n"; //i是质数for (int j = i; j <= n / i; j++) {v[i * j] = 1;}}
}

        Eratosthenes筛法的时间复杂度为O(NloglogN)。该算法实现简单，效率已经非常接近线性，是算法竞赛中最常用的质数筛法。

线性筛法：

        即使在优化后，Eratosthenes筛法仍然会重复标记合数。例如12既会被2又会被3标记，在标记2的倍数时，12 = 6 * 2，在标记3的倍数时 12 = 4 * 3。其根本原因是我们没有确定出唯一的产生12的方式。

        线性筛法通过"从大到小累积质因子" 的方式标记每个合数，即让12只有 3 * 2 * 2一种产生方式。设数组v记录每个数的最小质因子，我们按照以下步骤去维护v。

        1：依次考虑2 ~ N之间的每一个数 i 。

        2：若v[i] = i，说明 i 是质数，把它保存下来。

        3：扫描不大于v[i]的每个质数p，令v[i * p] = p，也就是在 i 的基础上累积一个质因子p。因为p<=v[i]，所以p就是合数 i * p 的最小质因子。

每个合数 i * p只会被它的最小质因子 p 筛一次，时间复杂度为O(N)。

constexpr int N = 5e6 + 10;
int v[N], prime[N], cnt;
void Getprimes(int n) {std::memset(v, 0, sizeof v);//最小质因子cnt = 0;for (int i = 2; i <= n; i++) {if (v[i] == 0) {v[i] = i; prime[++cnt] = i;//i 是质数}//给当前的数 i 乘上一个质因子for (int j = 1; j <= cnt; j++) {//i有比prime[j]更小的质因子,或者超出n的范围,停止循环if (prime[j] > v[i] || prime[j] > n / i) break;//prime[j] 是合数 i * prime[j] 的最小质因子v[i * prime[j]] = prime[j];}}for (int i = 1; i <= cnt; i++) {std::cout << prime[i] << "\n";}
}

质因数分解： 

算术基本定理

试除法：

         结合质数判定的"试除法"和质数筛选的"Eratosthenes筛法"，我们可以扫描2 ~ sqrt(N)的每一个数d，若d能整除N，则从N中除掉所有的因子d，同时累计除去的d的个数。

        因为每一个合数的因子一定在扫描到这个合数之前就从N中被除掉了，所以在上述过程中能整除N的一定是质数。最终就得到了质因数分解的结果，易知时间复杂度为O(sqrt(N))。

        特别地，若N没有被任何2 ~ sqrt(N)的数整除，则N是质数，无需分解。

constexpr int N = 1e5 + 10;
int p[N], c[N];void divide(int n) {int cnt = 0;for (int i = 2; i * i <= n; i++) {if (n % i == 0) {//i是质数p[++cnt] = i, c[cnt] = 0;while (n % i == 0) {n /= i;c[cnt]++;}}}if (n > 1) {//n 是质数p[++cnt] = n, c[cnt] = 1;}std::cout << p[1] << "^" << c[1];for (int i = 2; i <= cnt; i++) {std::cout << "*" << p[i] << "^" << c[i];}
}