当前位置:   article > 正文

质数和约数算法优化

质数和约数算法优化


提示:例题中的注释是精华

1 质数

质数:在大于1的整数中,如果只包含1和本身这两个约数,就被称为质数或素数

1.1 质数的判定——试除法

时间复杂度: n \sqrt{n} n

如果d能整除n的话,那么 n / d n/d n/d也能整除n
在枚举的时候只枚举d<= n / d n/d n/d的数 d < = n d <= \sqrt{n} d<=n 即可

1.1.1 模板

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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

1.1.2 例题

AcWing 866. 试除法判定质数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int n;

void isprime (int x)
{
    if(x < 2) {
        puts("No");
        return;
    }
    for (int i = 2; i <= x / i; i ++)
    {
        if(x % i == 0)
        {
            puts("No");
            return;
        }
    }
    puts("Yes");
}


int main ()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int x;
        scanf("%d", &x);
        isprime(x);
    }
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

1.2 分解质因数——试除法

非质数都可以分解成若干质数相乘的形式,而将其分解就是分解质因数
性质:n当中最多只包含一个大于 n \sqrt{n} n 的质因子
一个数的除了 1 之外最小的因数一定是质数

  1. 质因子: 能整除给定正整数的质数
  2. 每个合数都可以写成几个质数相乘的形式 x=p1p2…*pn
  3. 质因子如重复可以用指数表示
  4. 质数:只有一个质因子的正整数,质数>=2
  5. 1没有质因子
  6. 质数=素数,因数=约数

1.2.1 模板

时间复杂度最坏O( n \sqrt{n} n ),最好是 l o g n logn logn

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;//说明剩余的x是一个质数在根号n内没有因子了
    cout << endl;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

1.2.2 例题

AcWing 867. 分解质因数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;

void divide (int x)
{
    for (int i = 2; i <= x / i; i ++)// 优化循环次数,最后x单独判断
    {
        if (x % i == 0)// 因为是从小到大遍历所以,x的最小因数一定是质数,所以i一定是质数
        {
            int s = 0;// 这里s要定义到if内因为是每一个质数的指数
            while(x % i == 0) x /= i, s ++;// 把i这个因子除干净,后这样新的数的最小因子就又是比上个i大的新的质数
            printf("%d %d\n", i, s);
        }
    }
    if (x > 1) printf("%d %d\n", x, 1);// 最后x是质数的话根号n内他就没有因子了,就要将它输出
    cout << endl;
}

int main ()
{
    cin >> n;

    while (n -- )
    {
        int x;
        scanf("%d", &x);

        divide(x);
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

1.2 筛质数

一个数p如果不是1~p - 1的倍数就说明它是一个质数
质数定理:1~n中有 n ln ⁡ n \frac{n}{\ln{n}} lnnn个质数

埃氏筛法:是将一个数的倍数筛掉
线性筛法: n只会被它的最小质因子筛掉

1.2.1 内容

  • 从小到大枚举所有的质数
  • 每次将当前的质数和i的乘积筛掉
  • 当(i % primes[j] == 0)break;//此时primes[j] 一定是最小质因子

1.2.2 最简单的做法

i从2开始枚举将i的倍数标记成合数

时间复杂度是O(n log ⁡ n \log{n} logn)

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

void get_prime(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i]) primes[cnt ++] = i;

        for(int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

1.2.3 埃氏筛法

埃氏筛法是将上面的方法进行优化,这标记质数的倍数,但是存在重复标记的问题

时间复杂度:实际是O(nlogn logn),近似O(n)

// 朴素筛分求素数
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;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

1.2.4 线性筛法

线性筛法是将每个和数用它的最小质因子筛掉,且只用最小值因子筛掉,保证只筛一次,所以是线性的

时间复杂度:O(n)

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;
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
1.2.4.1 例题

AcWing 868. 筛质数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int primes[N], cnt;// primes[N]存放质数,cnt是下标也是质数的数量
bool st[N];
//线性筛法:为避免一个合数被重复筛,我们是用他的最小质因子来筛
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;//当不满足i % primes[j] 是说明primes[j] 不是i的最小质因子,那么primes[j] 就是primes[j] * i 的最小质因子
            if (i % primes[j] == 0) break;// 当i % primes[j] == 0时说明primes[j] 是i的最小质因子此时还满足 primes[j] 是 primes[j] * i 的最小质因子        }

            // 当是当进行下一次循环时,primes[j + 1] * i 因为i中有最小因子primes[j] 所以primes[j + 1] * i 就只能被primes[j] 筛掉,否则就重复筛了
        }
    }
}

int main()
{
    int n;
    cin >> n;

    get_primes(n);
    printf("%d", cnt);
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

2 约数

又称一个数的因数

2.1 试除法求约数

2.1.1 set容器的基本概念

  • 所有元素都会在插入set容器时自动排序
  • set/multiset属于关联式容器,底层是二叉树
  • set容器不允许存在重复元素
  • multiset允许存在重复元素

2.1.2 模板

时间复杂度:

void get_divisors(int x)
{
    set<int> s;
    for (int i = 1; i <= x / i; i ++)
    {
        if (x % i == 0) s.insert(i), s.insert(x / i);
    }
    for (auto item : s)
        printf("%d ", item);
    puts("");
    
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

2.1.3 例题

AcWing 869. 试除法求约数

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;

void get_divisors(int x)
{
    set<int> s;
    for (int i = 1; i <= x / i; i ++)
    {
        if (x % i == 0) s.insert(i), s.insert(x / i);// x能被i整除i是其中一个因数,那么另一个因数是x / i
    }
    for (auto item : s)// set容器会自动排序
        printf("%d ", item);
    puts("");

}
int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i ++)
    {
        int x;
        scanf("%d", &x);

        get_divisors(x);
    }
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33

2.2 约数和定理和约数个数定理

bilibili的up讲解

2.2.1 约数个数定理

内容:首先,分解质因数,这样通过利用质因数进行“造”约数就可以得到约数
而每个质因数都可以有0,1……n 这n + 1个取法
因此约数的个数就是将
约数个数: (c1 + 1) * (c2 + 1) * … * (ck + 1)

2.2.2 例题

AcWing 870. 约数个数

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int N = MOD = 1e9 + 7;
unordered_map<int, int> primes;


void divide(int x)
{
    for (int i = 2; i <= x / i; i ++)
    {
        while(x % i == 0) x /= i, primes[i] ++;// 不需要按顺序输出就不用按分解质因数那样用k记录
    }
    if (x > 1) primes[x] ++;
}

int main()
{
    int n;
    cin >> n;

    while (n --)
    {
        int x;
        scanf("%d", &x);

        divide(x);
    }

    LL res = 1;
    for (auto prime : primes)
        res = res * (prime.second + 1) % MOD; // 不能写成res *= 因为这样会先取模,而这样写就是后取模

    printf("%d", res);
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

2.2.3 约数和定理

通过“造”的方法,每个质因子与另外的一些质因子进行组合可以得到相应的组合:
(p1^0 + p1^1 + … + p1^c1) * … * (pk^0 + pk^1 + … + pk^ck)
在计算每一个pn时使用了秦九韶算法

简单来说就是将一个多项式层层剥离,最后剥成一个ax + b的形式而其中a是最前面一个次方的系数,b是后面一个次方的系数,计算的结果就可以作为下一个多项式的系数

2.2.4 例题

AcWing 871. 约数之和

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long LL;

const int N = 2e9, MOD = 1e9 + 7;
int n;

unordered_map<int, int> primes;

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++)
    {
        while (x % i == 0) x /= i, primes[i] ++;
    }
    if (x > 1) primes[x] ++;
}

int main()
{
    cin >> n;

    int sum = 0;
    for (int i = 0; i < n; i ++)
    {
        int x;
        scanf("%d", &x);
        divide(x);
    }

    LL res = 1;
    for (auto prime : primes)// 从这里处理用上了秦九韶算法,其余与求约数个数相同
    {
        int x = prime.first, k = prime.second;
        LL temp = 1;
        for (int i = 0; i < k; i ++)
            temp = (temp * x + 1) % MOD; // 当i = 0时一开始的系数是1,后面加1是因为后面的系数都是1,最后的系数也是1
        res = res * temp % MOD;
    }
    printf("%d", res);
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46

2.3 最大公因数

欧几里得算法
其中最关键的是(A, B) = (B, R) ->A和B的最大公因数和B和R的最大公因数相等,递推到最后可以发现余数为零时的R就是A, B的最大公因数

2.3.1 欧几里得算法(辗转相除法)

2.3.1.1 模板
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;//在最后一轮递归的过程中 a % b == 0 就说明余数为零, 返回的a是上一轮的b就是上面提到的R
}
  • 1
  • 2
  • 3
  • 4
2.3.1.2 例题

AcWing.872. 最大公约数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int gcd(int a, int b)
{
    return (b ? gcd (b, a % b) : a);
}

int main()
{
    int n;
    cin >> n;
    
    while (n -- ){
        int a, b;
        scanf("%d%d", &a, &b);
        
        printf("%d\n", gcd(a, b));
    }
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

3 参考文献

数学知识(一)
约数和定理和约数个数定理
秦九韶算法
欧几里得算法

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/609383
推荐阅读
相关标签
  

闽ICP备14008679号