202503021811 数论 质数

试除法判定质数 O(sqrt(n))

在大于 1 的整数中, 只包含 1 和本身两个约数, 就叫做质数 一个数是质数 ←> 该数只能被 1 和自身整除 如 7 的因子有 1 7, 为质数/素数; 6 的因子有 1 2 3 6, 不是质数 显然如果对于一个数 n, 如果在 [2, n-1] 这个范围内存在一个数 x 满足 n % x == 0, 说明 n 有除了 1 和 n 之外的因子 x, 也就不是质数, 反之则是质数

i ⇐ sqrt(x) ⇒ i ⇐ x / i 6: 1 2 3 6 4: 1 2 4

约数性质 1： 如果 d 是 n 的约数, 那么 n/d 也是 n 的约数

可以只枚举每对中较小的那个

for(int i = 2; i <= sqrt(n * 1.0); i++);
// 不推荐, 因为每次都要算 sqrt
for(int i = 2; i * i <= n; i++)
// 不推荐, 当n特别大时, ixi 可能溢出
for(int i = 2; i <= n / i; i++)
// 推荐

分解质因数 O(最大 sqrt(n))

定义： 把一个合数分解成若干个质因数的乘积的形式

根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。 n=p1^a1 * p2^a2 *p3^a3…pn

求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。

且只会出现一个 大于 sqrt(n) 的质因数。

从 2 开始枚举数, 每遇到一个质因数, 即 n % i == 0 且 i 为质数的数 就一直进行 n /= i 直到 i 不再是 n 的因数

这样便是从小到大分解质因数

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
 
int main()
{
    cin >> n;
    while(n--)
    {
        int x;
        cin >> x;
        for(int i = 2; i <= x / i; i++)
        {
            if(x % i == 0)
            {
                int s= 0;
                while(x % i == 0)
                {
                    x /= i;
                    s++;
                }
                cout << i << " " << s << endl;
            }
        }
        if(x > 1) cout << x << " " << 1 << endl;
        cout << endl;
    }
    return 0;
}

筛质数

从 2 到 n 每碰见一个质数就把他所有的倍数删去, 这样当遇到一个数 i 时, 1-i 中不存在 i 的约数, 故 i 就是质数

这就是埃氏筛：O(nloglogn)

bool st[N];
int prime[N], cnt;
for(int i = 2; i <= n;i ++)
{
	if(!st[i])
	{
		prime[cnt++] = i;
		for(int j = i + i; j <= n; j += i)
			st[j] = true;
	}
}

线性筛：

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

n 只会被它的最小质因子筛掉

1. i % prime[j] == 0 prime[j] 一定是 i 的最小质因子, prime[j] 一定是 i * prime[j] 的最小质因子
2. i % prime[j] != 0 说明 prime[j] 一定小于 i 的所有质因子, 也一定是 i * prime[j] 的最小质因子

对于一个合数 x, 在枚举到 x 之前肯定会枚举到最小质因子, 故筛掉, 且每个合数只会被筛一次

题目

类型	简介
阶乘分解质因数
质数距离
夏洛克和他的女朋友
哥德巴赫猜想