首页 > 编程语言 >算法笔记的笔记——第5章 数学问题

算法笔记的笔记——第5章 数学问题

时间:2023-03-20 21:33:53浏览次数:42  
标签:prime 因子 int 素数 笔记 ++ 算法 maxn 数学

简单数学

最大公约数与最小公倍数

  • 最大公约数

    int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
    
  • 最小公倍数

    假设d为a和b的最大公约数,则a和b的最小公倍数是a/d*b。

分数

素数

  • 除1和本身外不能被其他数整除的一类数
  • 1既不是素数也不是合数

素数的判断

  • 从2到sqrt(n)(下界)都不能被n整除就是素数

    bool isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        int sqr = (int)sqrt(1.0 * n);
        for (int i = 2; i <= sqr; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
    

素数表

  • 数据不超过105可以直接循环判断素数,复杂度O(n√n)

  • 线性筛:对每一个素数,筛去它的所有倍数,剩下的就是素数,复杂度O(nloglogn)

    const int maxn = 101;
    int prime[maxn], pNum = 0;
    bool p[maxn] = {0};
    
    void Find_Prime() {
        for (int i = 2; i < maxn; i++) {
            if (!p[i]) {
                prime[pNum++] = i;
                for (int j = i + i; i < maxn; j += i) {
                    p[j] = true;
                }
            }
        }
    }
    

质因子分解

  • 先打印素数表

  • 枚举1到sqrt(n)范围内的质因子p,判断p是否是n的因子

  • 如果p是n的因子,给fac数组增加质因子p,初始化个数为0,只要p还是n的因子,就让n除以p,每次令p的个数加1,直到p不再是n的因子

  • 如果p不是n的因子就跳过

  • 如果上述步骤结束后n仍然大于1,说明n有且仅有一个大于sqrt(n)的质因子,把它加入fac数组,令个数为1

    #include <cstdio>
    #include <cmath>
    
    const int maxn = 100010;
    int prime[maxn], pNum, num;
    bool notPrime[maxn];
    
    struct factor {
        int p, cnt;
    } fac[10];	// 对于int范围内的数数组大小开到10就够用了
    
    void Find_Prime() {
        for (int i = 2; i < maxn; i++) {
            if (!notPrime[i]) {
                prime[pNum++] = i;
                for (int j = i + i; j < maxn; j++) {
                    notPrime[j] = true;
                }
            }
        }
    }
    
    int main() {
        int n;
        scanf("%d", &n);
        int sqr = (int)sqrt(1.0 * n);
        Find_Prime();
        for (int i = 0; i < pNum && prime[i] <= sqr; i++) {
            if (n % prime[i] == 0) {
                fac[num].p = prime[i];
                fac[num].cnt = 0;
                while (n % prime[i] == 0) {
                    fac[num].cnt++;
                    n /= prime[i];
                }
                num++;
            }
        }
        if (n != 1) {
            fac[num].p = n;
            fac[num].cnt = 1;
            num++;
        }
        for (int i = 0; i < num; i++) {
            printf("%d %d\n", fac[i].p, fac[i].cnt);
        }
        return 0;
    }
    

    时间复杂度O(√n)。

标签:prime,因子,int,素数,笔记,++,算法,maxn,数学
From: https://www.cnblogs.com/secant1006/p/17237894.html

相关文章

  • 外设驱动库开发笔记52:PM3003S激光粉尘仪驱动
      空气质量是现代日常生活中人们所关注的事情,也是生存环境好坏的一种体现。其中粉尘数量监测更是空气质量检测中最常见的对象,在我们的检测设备中也经常会有这种需求。检......
  • 704.二分查找——学习笔记
    题目:给定一个n个元素有序的(升序)整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果目标值存在返回下标,否则返回-1。示例1输入:nums=[-1,0,3......
  • 35.搜索插入位置——学习笔记
    题目:给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。请必须使用时间复杂度为O(logn)的算法。......
  • 34.在排序数组中查找元素的第一个和最后一个位置——学习笔记
    题目:给你一个按照非递减顺序排列的整数数组nums,和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target,返回[-1,-1]。......
  • Boruvka 算法简记
    这个算法怕是只会存在于模拟赛里了。Boruvka算法是用于解决完全图的生成树的一类算法,因为完全图边数很多,因此普通时间复杂度基于边数的做法不适用。Boruvka算法核心思想......
  • [算法课]全面翻新计划!第二周全解
    文章目录​​上课内容​​​​试题A:组队​​​​数据​​​​详细分析​​​​颜老板版本暴力枚举​​​​吐槽​​​​更新版​​​​思路​​​​枚举版本​​​​思路......
  • [算法课]全面翻新计划!第十一周全解
    文章目录​​上课内容​​​​贪心法​​​​例1兑换货币​​​​颜老板代码​​​​更新版​​​​测试数据​​​​博主提示:​​​​注意:​​​​贪心算法的思路:​​​​......
  • Android studio学习笔记
    wrap_content内容有多少,它的宽度有多少match_parent匹配父空间,上一级宽度多少,这一级多少使用宽度长度自定义的时候最好用dp,因为Android屏幕碎片化比较严重,在不同的系统......
  • 《操作系统导论》读书笔记1——CPU虚拟化,进程
    系列文章目录和关于我一丶CPU的虚拟化一个桃子,我们称之为物理(physical)桃子。但有很多想吃这个桃子的人,我们希望向每个想吃的人提供一个属于他的桃子,这样才能皆大欢喜。......
  • 代码随想录算法训练营Day48 动态规划
    代码随想录算法训练营代码随想录算法训练营Day48动态规划|198.打家劫舍213.打家劫舍II337.打家劫舍III198.打家劫舍题目链接:198.打家劫舍你是一个专业的小偷,计划偷......