算法基础课 第四讲 数学知识——质数

定义：

质数是指在大于$1$的自然数中，除了$1$和它本身以外不再有其他因数的自然数。

难题：(非学习重点！了解即可)

哥德巴赫猜想
黎曼猜想
孪生质数
梅森素数

试除法判定质数

基本判断思路

质数大于等于$2$ 不能被它本身和$1$以外的数整除
在一般领域，对正整数$n$，如果用$2$到$ \sqrt{n} $之间的所有整数去除，均无法整除，则$n$为质数。

时间复杂度 $ O(\sqrt{n}) $(稳定)

$C++$代码：

$first$(无优化)
(模板题 AcWing 866. 试除法判定质数)

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

$second$(优化版)

bool isPrime(unsigned long n)
{
    if (n <= 3)
        return n > 1;
    else if (n % 2 == 0 || n % 3 == 0)
        return false;
    else 
    {
        for (unsigned short i = 5; i * i <= n; i += 6) 
            if (n % i == 0 || n % (i + 2) == 0) 
                return false;
        return true;
    }
}

试除法分解质因数

思路：

暴力枚举 从小到大尝试$ n $ 的所有因数
优化 不必循环$ n $次,循环$ \sqrt{n} $次即可

时间复杂度:理论 $O(\sqrt{n})$ ,最好 $O(㏒n)$,最坏$O(\sqrt{n})$

$C++$代码：

(模板题 AcWing 867. 分解质因数)

void divide(int 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;
    // n中最多只包含一个大于√n的质因子，单独处理即可
    // 如果n中包含两个大于√n的质因子a和b,那么a*b>n,不成立,所以n中最多只包含一个大于√n的质因子.证毕.
    cout << endl;
}

说明：

if (x % i == 0)
被枚举的数一定是质数
合数是由质数构成的,所以在枚举质数时,就相当于枚举了其相应的合数
在枚举合数时,由上面的结论得,该合数已经被枚举,所以被枚举的数一定是质数.证毕.
if (x > 1) cout << x << ' ' << 1 << endl;
n中最多只包含一个大于$\sqrt{n}$的质因子，单独处理即可
如果n中包含两个大于$\sqrt{n}$的质因子$a$和$b$,那么$a*b>n$,不成立,所以$n$中最多只包含一个大于$\sqrt{n}$的质因子.证毕.

筛质数

模板题AcWing 868. 筛质数

埃氏筛法

简介

埃拉托色尼筛选法($the Sieve of Eratosthenes$)简称埃氏筛法,是古希腊数学家埃拉托色尼($Eratosthenes 274B.C.～194B.C.$)提出的一种筛选法.是针对自然数列中的自然数而实施的,用于求一定范围内的质数,它的容斥原理之完备性条件是$p=H～$.

步骤

1.先把1删除（现今数学界$1$既不是质数也不是合数）
2.读取队列中当前最小的数$2$，然后把$2$的倍数删去
3.读取队列中当前最小的数$3$，然后把$3$的倍数删去
4.读取队列中当前最小的数$5$，然后把$5$的倍数删去
5.读取队列中当前最小的数$7$，然后把$7$的倍数删去
6.如上所述直到需求的范围内所有的数均删除或读取
注：此处的队列并非数据结构队列，如需保留运算结果，出于存储空间的充分利用以及大量删除操作的实施，建议采用链表的数据结构。

时间复杂度 $O(n㏒㏒n)$

C++代码

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

线性筛法

思路

时间复杂度 $O(n)$

C++ 代码实现

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

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