算法竞赛进阶指南 第四章 质数

算法竞赛进阶指南 第四章 质数

- 8 mins
markdown components extra

数学知识

质数

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

对于一个足够大的整数N,不超过N的质数大约有N/lnN个,即每lnN个数中大约有1个质数

质数的判定

试除法

我们只需要扫描2~genhaoN之间的所有整数,依次检查它们能否整除N,若都不能整除,则N是质数,否则N是合数

特判0和1这两个整数,它们既不是质数,也不是合数

bool is_prime(int n)
{
    if(n < 2) return false;
    for(int i = 2; i <= sqrt(n); i++)
        if(n % i == 0) return false;
    return true;
}

Miller-Robbin(效率更高的随机性算法,有较小概率把合数错误判定为质数,但多次判定合起来的错误概率趋近于零)

质数的筛选

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

Eratosthenes筛法(O(NloglogN))

任意整数x的倍数都不是质数.

image-20230203095546733

void primes(int n)
{
    memset(v,0,sizeof(v));
    for(int i = 2; i <= n; i++)
    {
        if(v[i]) continue;
        cout << i << endl;
        for(int j = i ; j<= n/i; j++) v[i*j] = i;
    }
}

线性筛法O(N)

通过”从大到小积累质因子”的方式标记每个合数,即让12只有322一种产生方式.

设数组v记录每个数的最小质因子,我们按照以下步骤维护v

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

2.若v[i] = i,说明i是质数

3.扫描不大于v[i]的每个质数p,令v[ip] = p.也就是在i的基础上积累一个质因子p,p就是合数ip的最小质因子

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

int v[MAX_N],prime[MAX_N];
void primes(int n)
{
    memset(v,0,sizeof(v));
    m = 0;//质数数量
    for(int i = 2; i <= n; i++)
    {
        if(v[i] == 0)
        {
            v[i] = i;
            prime[++m] = i;
        }
        for(int j = 1; j <= m; 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 <= m; i++) cout << prime[i] << endl;
}

质因数分解

算术基本定理

任何一个大于1的正整数都能唯一分解为有限个质数的乘积

试除法(O(sqrt(N))

结合质数判定的”试除法”和指数筛选的”Eratosthenes筛法”,我们可以扫描2~根号N的每个数d,若d能整除N,则从N中除掉所有的因子d,同时累计除去的d的个数

void divede(int n)
{
    m = 0;
    for(int i = 2; i <= sqrt(n); i++)
    {
        if(n % i == 0)
        {
            p[++m] = i,c[m] = 0;
            while(n % i == 0) n/=i, c[m]++;
        }
    }
    if(n > 1)
        p[++m] = n, c[m] = 1;
    for(int i = 1; i <= m; i++)
        cout << p[i] << '^' << c[i] << endl;
}

Pollard’s Rho算法是一个比”试除法”效率更高的质因数分解算法

Prime Distance

L,R的范围很大,任何已知算法都无法在规定时间内生成[1,R]中的所有质数

但R-L的值很小,并且任何一个合数n必定包含一个不超过sqrt(n)的质因子

解:用筛法求出2~sqrt(R)之间的所有质数.对于每个质数p,将范围内其倍数标记,未被标记的即为合数

(这里的标记也可以用下题中,选倍数的方法,可以进一步优化时间复杂度)

image-20230203113755606

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int l, u;
    int v[1 << 16];
    bool jud[1000005];
    while (cin >> l >> u)
    {
        if (l == 1)
            l++;
        memset(jud, 0, sizeof(jud));
        vector<int> su;
        su.clear();
        memset(v, 0, sizeof(v));
        for (int i = 2; i <= sqrt(u); i++)
        {
            if (v[i])
                continue;
            // 素数运算,i为素数
            for (int j = ceil(l / i); j <= floor(u / i); j++)
            {
                if (j == 1)
                    continue;
                jud[i * j - l] = 1;
            }
            for (int j = i; j <= sqrt(u) / i; j++)
                v[i * j] = i;
        }
        int maxx = 0, leftt, r;
        for (int i = 0; i <= u-l; i++)
        {
            if (!jud[i])
            {
                su.push_back(i+l);
            }
        }
        if (su.size() < 2)
            cout << "There are no adjacent primes.\n";
        else
        {
            int ans_l, ans_r, ansl2, ansr2, l2, r2, minn;
            ansl2 = ans_l = leftt = l2 = su[0], ansr2 = ans_r = r = r2 = su[1];
            maxx = minn = r - leftt;
            for (int i = 2; i < su.size(); i++)
            {
                leftt = r;
                r = su[i];
                if (maxx < r - leftt)
                {
                    maxx = r - leftt;
                    ans_l = leftt;
                    ans_r = r;
                }
                if (minn > r - leftt)
                {
                    minn = r - leftt;
                    ansl2 = leftt;
                    ansr2 = r;
                }
            }
            printf("%d,%d are closest, %d,%d are most distant\n", ansl2, ansr2, ans_l, ans_r);
        }
    }
    return 0;
}

注意点:map不能轻用,其添加,存取,删除的时间复杂度为log(n),不是O(1)

阶乘分解

先筛出1~N的每个质数p,然后考虑阶乘N!中一共包含多少个质因子p

image-20230203111840274

对于每个p只需要用O(logN)的时间计算上述和式,总时间复杂度为O(NlogN)

#include <bits/stdc++.h>
using namespace std;
int v[1000005];
vector<int> su;
int main()
{
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++)//埃氏筛法
    {
        if (v[i])
            continue;
        su.push_back(i);
        for (int j = i; j <= n / i; j++)
            v[i * j] = i;
    }
    for (int i = 0; i < su.size(); i++)//加和运算
    {
        int sum = 0;
        int p = su[i];
        for (int j = 1; j <= floor(log(n) / log(su[i])); j++)
        {
            sum += floor(n / p);
            p *= su[i];
        }
        cout << su[i] << ' ' << sum << '\n';
    }
    return 0;
}

Related Posts