小指针

V1

2022/03/17阅读:77主题:凝夜紫

重生之回到小学做数学(质数)

质数

质数又叫素数,是指在大于1的自然数中,除了1和它本身以外不在有其它因数的自然数。2是最小的质数。

因数是指整数a除以整数b(b≠0) 的商正好是整数而没有余数,我们就说b是a的因数。

判断一个数n是否是质数。

判断方法

明确概念之后,接下来的问题是如何判定某个数是否是质数呢?

一个标准的方式是使用试除法

试除法

用n除以2到 的所有整数,若其中没有可以整除的,则可以认定n是一个质数。

这里有一个问题是为什么试除法判断到 就可以,而无需除到n本身呢?

这是因为自然数的因数都是成对出现的。比如:12的因数有2和6,3和4。

既如此,我们只需要枚举较小的那个因数即可,而较小因数中的最大那个也不会超过

以下为数学证明:
假设较小的因数为d,那么较大的因数则为 ,公式表示为 ,推出 ,最终得到结论

Code

参考题目: AcWing 866. 试除法判定质数
题目链接:https://www.acwing.com/problem/content/868/

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i <= n // i:
        if n % i == 0:
            return False
        i += 1
    return True
    
n = int(input())
for _ in range(n):
    print('Yes' if is_prime(int(input())) else 'No')

分解质因数

给定 n 个正整数 ai,将每个数分解质因数,并按照质因数从小到大的顺序输出每个质因数的底数和指数。

比如:将数字12分解成质因数就是2*2*3,那么其中共有两个质因数,分别是2和3。其中2的指数是2,3的指数是1。即12分解质因数后结果为

分解质因数方法

那么如何分解质因数呢?先要理解如下性质:

  1. n 的质因子只能有一个大于 的数。因为如果存在两个大于 的数,这两个数的乘积一定会大于n 。
  2. 每个正整数都能以唯一的方式表示成它的质因数乘积。换言之,对于每个正整数来说,它的质因数乘积的结果是唯一的。

明确上面两个性质,不难理解分解质因数需要如下步骤:

  1. 枚举2到 为 i 。
  2. n去除以i判断余数,则有两种情况。
  3. 如果余数为0,说明in的质因子之一。
  4. cnt表示当前质因子i的指数,则有如下伪代码:
    while ((n % i) == 0){
        cnt ++;
        n /= i

    伪代码对应的作用是求出当前质因数i的个数。比如当前n是12,当前i是2,则一轮循环过后n变成6,下一轮循环6又能提供一个质因数2。如此,最终将n分解成为最小的质因数。

Code

参考题目: AcWing 867. 分解质因数
题目链接:https://www.acwing.com/problem/content/869/

def find(x):
    i = 2 
    while i <= x // i:
        # 如果i是质因子则判断个数
        if x % i == 0:
            cnt = 0
            while x % i == 0:
                cnt += 1
                x //= i
            print(f'{i} {cnt}')
        i += 1
    if x > 1:
        print(f'{x} 1')
    print('')

n = int(input())
for _ in range(n):
    find(int(input()))

筛质数

参考题目: AcWing 868. 筛质数
题目链接:https://www.acwing.com/problem/content/870/

给定一个正整数 n,请你求出 1∼n 中质数的个数。

例如:此时n为12,那么需要判断的就是1~12中所有的质数。(下面例子中,如无特殊说明,n也是12。)

1. 普通的翻倍筛选

操作方式

普通的翻倍筛法非常简单。

翻倍筛法的做法是,从最小的质数2枚举到n,依次判断是否是质数。在枚举的同时把枚举到的数翻倍,翻倍后得到的数一定不是质数(原因参考质数定义),因此可以直接筛掉。

比如:当前枚举到了2,持续将2翻倍就可以筛选掉4,6,8,10,12;接下来枚举到了3,持续将3翻倍就可以筛掉6,9,12。以此类推直到枚举完成,就选出了所有的素数。

Code

从代码循环次数中可以看出,这种做法的时间复杂度是

n = int(input())
N = 1000010
st = [0] * N # 标记是不是质数
p = [0] * N # 质数数组

def get_primes(n):
    cnt = 0 # 质数数组下标 同时统计个数
    for i in range(2, n + 1):
        if not st[i]: # 判断是否是质数
            p[cnt] = i
            cnt += 1
        j = i + i # 翻倍筛选
        while j <= n: # 循环结束
            st[j] = 1
            j += i
    return cnt

2. 埃氏筛

之所以叫埃氏筛,是因为这种筛质数的方式是一个叫埃拉托斯特尼的希腊数学家提出的。

操作方式

仔细观察普通筛法的操作,无论质数还是合数都用来做了翻倍筛选。也就是当枚举到4的时候,将4翻倍筛掉812,可是在枚举2的时候812已经被筛掉了,也就是做了冗余的工作。

埃氏筛就是去掉了这部分冗余工作,也就是说合数不再用来筛选,转而只使用质数筛选

Code

在代码上的体现就是把普通筛法中的用于筛选的循环放到只有枚举到质数的时候才执行。

这种方法的时间复杂度是 ,这个复杂度其实已经无限接近

def get_primes(n):
    cnt = 0
    for i in range(2, n + 1):
        if not st[i]:
            p[cnt] = i
            cnt += 1
            # 下面循环是翻倍筛选
            j = i + i
            while j <= n:
                st[j] = 1
                j += i

    return cnt

线性筛

尽管埃氏筛的复杂度已经足够小,但是还不是真正的线性算法。还有一种真正 时间复杂度的筛法,称为线性筛。

操作方式

线性筛的操作非常之巧妙,在了解线性筛之前,我们先看一下埃氏筛是否存在冗余操作。

按照埃氏筛的逻辑,只用质数翻倍筛选。那么,当枚举到2的时候,会进行翻倍筛选,10会被筛掉;继续枚举当枚举到5的时候,我们知道5也是质数,那么5进行翻倍筛选,又筛掉了一遍10,这也就是埃氏筛的冗余操作。

线性筛就是解决了埃氏筛的这一部分冗余操作,即每个合数只会被它的最小的质因子筛掉

这样,10的最小质因子是2,那么它只会被2筛掉,而不会遇到5再被筛一次。

Code
def get_primes(n):
    cnt = 0
    for i in range(2, n + 1):
        if not st[i]:
            p[cnt] = i
            cnt += 1
        # 循环2
        j = 0
        while p[j] <= n // i:
            st[p[j] * i] = 1
            # 结束条件
            if i % p[j] == 0:
                break
            j += 1
    return cnt

线性筛从代码中标记的循环2的部分开始与前面两种筛法出现明显不同。

循环2的循环条件是p[j]<=n//i,变形一下就是p[j]*i<=n,与上面两种筛法的循环条件就比较类似了。而p[j]*i正是每次筛选掉的合数。

而循环结束条件i%p[j]==0正是线性筛最精妙的部分。可以从两方面理解这一条件的含义。理解的基础是要始终明确一个概念,那就是p数组中的质数是递增的(2,3,5...)

  1. 那么,当i遇到第一个能整除的pj时,pj一定是i的最小质因子,所以,pj也一定是pj*i的最小质因子。

    比如,i9pj3。此时,pji的最小质因子,那么pj也一定是pj*i=27的最小质因子。

  2. i无法整除pj时,也就是i%pj!=0,一定有pj小于i的最小质因子,也就是小于i的所有质因子,那么pj还是pj*i的最小质因子。

    比如,i7pj3。此时,pj一定是pj*i=21的最小质因子。

试想一下,没有这个循环结束条件会发生什么?

n=12的例子中,没有结束条件,则出现如下状况:

  1. i4时候,p为[2,3]pj2pj*i筛掉8
  2. 执行j+1后,pj变成3
  3. pj*i筛掉12
  4. 继续枚举,当i6pj2的时候,满足循环条件,于是又筛掉一遍12

于是我们惊奇的发现,12这个数字被重复筛掉,与线性筛的基本原则(每个合数只被它的最小质因子筛掉)不符

综上,这个精妙的结束条件,才是线性筛中最重要的部分。

总结

本文粗略的描述了质数及一些与之相关的概念。并解决了三个问题。分别是:

  1. 判断一个数是否是质数;
  2. 分解质因数;
  3. 判断出1~n中有多少质数;

END

分类:

数学

标签:

数学编程

作者介绍

小指针
V1