质数相关算法_1到n 质数

质数定义：若一个大于2的自然数，只有1和它本身两个因子，则这个数为素数。
质数判定：试除法。

bool check(int n) {
    if (n < 2) return false;
	for (int i = 2; i <= n / i; i++)
		if (n % i == 0) return false;
	return true;
}
1
2
3
4
5
6

质数定理：1 - n中有大约有 n / lnn 个质数。
调和级数：1 + 1/2 + 1/3 + … + 1/n = lnn + C(常数)。
算数基本定理：任何一个大于1的自然数 N，如果N不为质数，那么N可以唯一分解成有限个质数的乘积N = P1 ^a1P2^a2P3^a3…Pn^an，这里P1<P2<P3…<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式。
质因数分解：试除法。

void divide(int n) {
    for (int i = 2; i <= n / i; i++) {
        int s = 0;
        while (n % i == 0) {
            n /= i;
            s++;
        }
        if (s) cout << i << " " << s << endl;
    }
    if (n > 1) cout << n << " " << "1" << endl;
}
1
2
3
4
5
6
7
8
9
10
11

我每当遇到一个当前n的因数就将其从n中全部除去，这时的因数一定是质数，因为当前的n已经不含2 - i-1 的所有因数，而n是i的倍数，所以i也不含2 - i-1的所有因数，所以i是质数。
每当我从n中除掉当前质因数时，问题就变为一个新的n的子问题，对于每个新的n来讲，我只要枚举 i+1 - 根号n即可，因为新的n必然不包含2 - i的因数，且一个数在质因数分解式中最多出现一个大于根号n的质因数，于是只要在最后判断一下最后的n是否大于1即可。
筛质数：
（1）埃氏筛：

for (int i = 2; i <= n; i++) {
		if (!st[i]) {
		    prime[++cnt] = i;
            for (int j = i; j <= n; j += i) st[j] = true; //只需筛质数的倍数，合数的倍数一定在筛素数的倍数时就被筛掉了，其实还可以加一个小优化，就是从i * i开始筛，因为2 * i - (i - 1) * i一定在之前已经被晒过了
		}
	}
1
2
3
4
5
6

（2）线性筛：核心思想：每个合数只会被它的最小质因子筛掉。
我们主要说明以下两点：

1. 每个合数只会被筛一次（是线性的）
2. 所有合数都会被是筛掉
   先给出代码：

for (int i = 2; i <= n; i++) {
	if (!st[i]) prime[++cnt] = i;
	for (int j = 1; prime[j] <= n / i; j++) {
		st[prime[j] * i] = true;
		if (i % prime[j] == 0) break;
	}
}
1
2
3
4
5
6
7

1.从小到大枚举每个质数p，在发生i % p == 0之前，说明p与i的质因子没有交集，则说明此时p是i * p的最小质因子。当发生i % p == 0是， 说明此时p是i的最小质因子，那么p同样是i * p的最小质因子。当p再大时，p无论i % p == 0还是 i % p != 0，p都不在是i * p的最小质因子。所以应该在i % p == 0时break。由于每次我标记一个数是合数时，我都是用它的最小质因子筛的，所以每个数一定只会被筛一次。
2.设一个合数x，x的最小质因子为p，当i枚举到x / p时，无论x质因数分解中p的次数等于1还是大于1，st[prime[j]] * i都会被执行，所以x一定会被筛掉，由x的任意性知，所有的合数均会被筛掉。
例题：
题目链接
题目大意：给出一个分数a/b，构造一组c, d, e, f，使得c/d - e/f = a/b。
其中d<b, f<b, 1=<c, d<= 4e12。
题目分析：如果不考虑d<b,f<b的话可以直接用(a+b)/b -1来构造，当然当a和b不互质的话可以这样构造。
当a和b互质时，我们可以先将b分解为两个互质的因子的乘积，然后只要满足cf-de=a即可。这个可以用扩展欧几里得来解。至于为什么要将b分解为两个互质因子的乘积是因为由扩展欧几里得ax+by=gcd(a,b)，如果a,b不互质那么gcd(a,b)>1，但是a未必可以被gcd(a,b)整除。如果b不能分解为两个质因子的乘积，那么就属于无解的情况。
证明：
由于gcd(a,b)=1，即b的标准质因式分解与a不重合，设gcd(d,f)=k, 那么k必然在b的标准质因式分解中，所以此时a必然不能被k整除，于是也就无法进行构造。