C++算法之旅、08 基础篇 | 质数、约数

这篇具有很好参考价值的文章主要介绍了C++算法之旅、08 基础篇 | 质数、约数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

质数

在>1的整数中,如果只包含1和本身这两个约数,就被称为质数(素数)


866 试除法判定

866. 试除法判定质数 - AcWing题库

\(O(n)\)

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

约数 d 与 n / d 成对出现,可以枚举较小的那一个 \(O(\sqrt{n})\)

\(d <= n/d \\ d^2 <= n \\ d <= \sqrt{n}\)

难点

  • 循环判断条件不要用 sqrt,每次循环都会执行一遍sqrt函数,比较慢
  • 循环判断条件不要用 i * i,存在溢出风险(变成负数)
  • 一定不会溢出的写法是 i <= n / i
#include <iostream>

using namespace std;

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

int main() {
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        if (isprime(x))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

867⭐分解质因数

867. 分解质因数 - AcWing题库

质因数指能整除给定正整数的质数。把一个合数分解成若干个质因数的乘积的形式,即求质因数的过程叫做分解质因数。

相关理论证明可看 数论——质数:分解质因数 - 知乎 (zhihu.com)

从2到\(\sqrt{n}\)枚举n的所有质因数,求其指数并输出。还要考虑最多有一个质因素大于\(\sqrt{n}\)的情况,单独判断输出。 最坏 \(O(\sqrt{n})\),最好 \(O(logn)\) (考虑\(2^k\)情况)

#include <iostream>

using namespace std;

void divide(int n) {
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                cnt++;
                n /= i;
            }
            cout << i << " " << cnt << endl;
        }
    }
    if (n > 1) cout << n << " " << 1 << endl;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        divide(x);
        cout << endl;
    }
}

868⭐筛质数

868. 筛质数 - AcWing题库

朴素算法是从前往后删倍数(2~p-1都不是n的约数,所以n是质数)

调和级数\(1/2+1/3+1/4+1/5+...+1/∞\) 极限等于 \(lnn+C\)

\(lnn < log_2n\),因此朴素算法复杂度为 \(O(nlogn)\)


埃式筛法:只删除2~p-1中质数的倍数,原理跟867类似(算数基本定理:每个正整数都可以唯一表示成素数的乘积)

粗略估计:1~n当中,有\(n/lnn\)个质数,时间复杂度变为 \(O(n)\),真实复杂度 \(O(nloglogn)\),两者差不多一个级别

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];

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

int main() {
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;

    return 0;
}

线性筛法,\(O(n)\),基本思路一样(基于每个质数的倍数为非质数),当 n 很大时,速度比埃式筛法快一倍。

每个数只会被其最小质因子筛掉

  • i % pj == 0,pj 一定是 i 的最小质因子,pj 一定是 pj * i 的最小质因子
  • i % pj != 0,pj 一定小于 i 的所有质因子,pj 一定是 pj * i 的最小质因子
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int 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] * i <= n; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;  // primes[j] 一定是 i 的最小质因子
        }
    }
}

int main() {
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;

    return 0;
}

约数

869 试除法求约数

869. 试除法求约数 - AcWing题库

与866优化原理类似 \(O(\sqrt{n})\)

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<int> get_divisors(int n) {
    vector<int> res;
    for (int i = 1; i <= n / i; i++) {
        if (n % i == 0) {
            res.push_back(i);
            if (i != n / i) res.push_back(n / i);  // 避免平方
        }
    }
    sort(res.begin(), res.end());
    return res;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        auto res = get_divisors(x);
        for (auto t : res) cout << t << ' ';
        cout << endl;
    }
}

870⭐约数个数

利用算术基本定理,每个质因数有(1+n)种选择。m个选择组合得出m个约数

具体原理可看 第四章 数学知识(一)——质数与约数 - 知乎 (zhihu.com)

INT_MAX 约数个数约1500


870. 约数个数 - AcWing题库

求 n 个数的乘积的约数个数,可以求每个数的每个质因子指数之和,然后套用公式。

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

using namespace std;

typedef long long LL;
const int mod = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    unordered_map<int, int> primes;
    while (n--) {
        int x;
        cin >> x;
        for (int i = 2; i <= x / i; i++) {
            while (x % i == 0) {
                x /= i;
                primes[i]++;
            }
        }
        if (x > 1) primes[x]++;
    }
    LL res = 1;
    for (auto prime : primes) res = res * (prime.second + 1) % mod;
    cout << res << endl;
    return 0;
}

871⭐约数之和

AcWing 871. 约数之和 - AcWing

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

using namespace std;

typedef long long LL;
const int mod = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    unordered_map<int, int> primes;
    while (n--) {
        int x;
        cin >> x;
        for (int i = 2; i <= x / i; i++) {
            while (x % i == 0) {
                x /= i;
                primes[i]++;
            }
        }
        if (x > 1) primes[x]++;
    }
    LL res = 1;
    for (auto prime : primes) {
        int p = prime.first, a = prime.second;
        LL t = 1;
        while (a--) {
            t = (t * p + 1) % mod;
        }
        res = res * t % mod;
    }
    cout << res << endl;
    return 0;
}

872⭐最大公约数

872. 最大公约数 - AcWing题库

欧几里得算法(辗转相除法)文章来源地址https://www.toymoban.com/news/detail-711708.html

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

using namespace std;

// a 和 0 的最大公约数是 a
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main() {
    int n;
    cin >> n;
    while (n--) {
        int a, b;
        cin >> a >> b;
        cout << gcd(a, b) << endl;
    }
    return 0;
}

到了这里,关于C++算法之旅、08 基础篇 | 质数、约数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++算法之旅、06 基础篇 | 第四章 动态规划 详解

    状态表示 集合 满足一定条件的所有方案 属性 集合(所有方案)的某种属性(Max、Min、Count等) 状态计算(集合划分) 如何将当前集合划分成多个子集合 状态计算相当于集合的划分 :把当前集合划分成若干个子集,使得每个子集的状态可以先算出来,从而推导当前集合状态

    2024年02月09日
    浏览(36)
  • C++算法之旅、05 基础篇 | 第二章 数据结构

    常用代码模板2——数据结构 - AcWing 使用结构体指针,new Node() 非常慢,创建10万个节点就超时了,做笔试题不会用这种方式(优化是提前初始化好数组,但这样跟数组模拟没区别了,而且代码量很长) 使用两个数组,e存储val,ne存储next。空节点next用-1表示 826. 单链表 - AcWi

    2024年02月10日
    浏览(58)
  • c++入门必学算法 质数筛

    质数筛也叫素数筛,是求1到n之内素数的优化算法,质数筛有两种,埃氏筛和欧拉筛。 埃氏筛的时间复杂度接近O(n*logn),而欧拉筛可以把复杂度降低到O(n),下面看两种算法的到底是如何一步步优化的吧 暴力法求解复杂度O(n)* n sqrt{n} n ​ ,是新手必学的算法,能解决小数据的

    2023年04月21日
    浏览(33)
  • e[2333333, 23333333] 中有多少个正整数 可以被分解为 12 个质数相乘?

    任何一个大于 1 的正整数都能被分解为若干个质数相乘, 比如 28=2 times 2 times 728=2×2×7 被分解为了三个质数相乘。请问在区间 [2333333, 23333333] 中有多少个正整数 可以被分解为 12 个质数相乘? 答案提交 这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一

    2023年04月08日
    浏览(43)
  • C++ 数论相关题目(约数)

    给定 n 个正整数 ai ,对于每个整数 ai ,请你按照从小到大的顺序输出它的所有约数。 输入格式 第一行包含整数 n 。 接下来 n 行,每行包含一个整数 ai 。 输出格式 输出共 n 行,其中第 i 行输出第 i 个整数 ai 的所有约数。 数据范围 1≤n≤100 , 1≤ai≤2×109 输入样例: 2 6 8 输

    2024年01月19日
    浏览(44)
  • C++算法之旅、03 语法篇 | 全内容

    cstdio 有两个函数 printf,scanf 用于输出和输入 iostream 有 cin 读入,cout 输出 使用了std命名空间,cin、cout定义在该命名空间中,不引入空间会找不到导致出错 函数执行入口 ⭐所有 cout、cin 都能用 scanf、printf 替换,但反过来,由于cout、cin效率可能较低会导致超时 ⭐ printf %c 会读

    2024年02月10日
    浏览(50)
  • C++ 算法竞赛、08 周赛篇 | AcWing 第94场周赛 ⭐

    4870. 装物品 - AcWing题库 4870. 装物品 - AcWing题库 巨简单题 4871. 最早时刻 - AcWing题库 考查堆优化版迪杰斯特拉变形 越早到达,越早离开 = 每个点维护一个最早到达时刻 如果 delay 小于 0,就不能用迪杰斯特拉算法 4872. 最短路之和 - AcWing题库 最终结果可能是 (500^2 * 10^5) 可能会

    2024年02月08日
    浏览(49)
  • Leetcode日记 9. 回文数 给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。

    给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。 回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。 例如,121 是回文,而 123 不是。 示例 1: 输入:x = 121 输出:true 示例 2: 输入:x = -121 输出:false 解释:从左向右读, 为 -121 。

    2024年02月21日
    浏览(39)
  • 数论 --- 约数和定理公式推导、最大公约数、欧几里得算法

    和试除法判断一个数是不是质数是一个道理 从小到大枚举所有的约数,如果当前数能整除这个数的话,说明这个数就是当前数的约数 优化,与试除法判断质数是一样的 如果 d 是 n 的约数,n / d 也一定能整除 n,一个数的约数也一定是成对出现的,在枚举的时候也可以只枚举

    2023年04月08日
    浏览(86)
  • LeeCode前端算法基础100题(17)- 罗马数字转整数

    罗马数字包含以下七种字符:  I ,  V ,  X ,  L , C , D  和  M 。 例如, 罗马数字  2  写做  II  ,即为两个并列的 1 。 12  写做  XII  ,即为  X  +  II  。  27  写做   XXVII , 即为  XX  +  V  +  II  。 通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特

    2024年01月19日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包