数论基础 2025.2.10

1 .质数筛 是否为质数

质数-若一个正整数无法被除了1和它自身之外的任何自然数整除,则称该数为 质数(prime)

否则称该正整数为 合数(Composite number)

  1. 试除法(定义)

      patr A
      bool Is_Prime(int x){
      if(x<2) return 0;
      for(int i=2;i<=x-1;i++)
          if(x%i==0) return 0;
      return 1;
     }
     part B
     bool Is_Prime(int x){
     if(x<2) return 0;
     for(int i=2;i*i<=x;i++)
         if(x%i==0) return 0;
      return 1;
     }
    

    一个数如果有因数,一定是一个大于一个效应 或者就是所以只要枚举1~

    2.埃氏筛oioioioio

    每个质数的倍数就是合数

     bool Check[];
     void Get_Prime(int n)//1~n{
         for(int i=2;i<=n;i++)
           if(!Check[i]){
             for(int j=2;i*j<=n;j++)
                 Check[i*j]=1;
          }
     }
    

    3 .线性筛

    埃氏筛会重复标记 12—既是3的倍数也是2的倍数

    所以线性筛!首先,任意一个合数都可以被分解成一个质数和一个数的积。对于任意一个合数,我们用“这个合数 = 最小质因数 × 最大因数(非自己)”,来表示

    bool Is_Prime[];
    int Prime[],top=0;
    void Get_Prime(int n){
          for(int i=2;i<=n;i++){
              if(!Is_Prime[i]) Prime[++top]=i;
              for(int j=1;i<=Prime[j]*i<=n&&j<=Top;j++){
                  Is_Prime[i*Prime[j]]=1;
                  if(i%Prime[j]==0) break;
              }
          }
    }  
    

2.欧拉函数(Euler's totient function) 欧拉

,若的最大公因数为1,即 互质

就是1~n中与n互质的数的个数

将n分解质因数可得

  • [推导]

  • 分解质因数后这些质因数在1~n中的倍数就是不能对产生贡献的数,举个粒子: 那么在中 2 ,3 ,5 的倍数就无法与300互质1-300中有个2的倍数,有个3的倍数,有个5的倍数

    同理 6 既是2的倍数也是3的倍数

    10 既是2的倍数也是5的倍数

    15 既是5的倍数也是3的倍数

    这些数每个被减了两遍所以要加回来

    1-300中有个6的倍数......

    所以这么多个数与300不互质

    转化一下

    然后因式分解

    !

    再来一个??

    !!!

    int Got_Phi(int x){//找x的欧拉值
        int ans=x;//初始认为全与x互质 
        for(int i=2;i*i<=x;i++){
            if(x%i==0){//i是x的因数
              ans=ans*((i-1)/i);//如公式
              while(x%i==0) x/=i;//把次方剔除
            }
         }
        if(x>1) ans=ans*((x-1)/x);//x自己是质数
        return ans;
    }
    
全部评论
upup,你的数论确实很强,但还是太吃操作了,有没有什么简单又强势的方法???
1 回复 分享
发布于 02-10 21:17 四川

相关推荐

白火同学:只是实习的话,你这份简历应该也差不多了。真要优化的话,因为面实习的话,没有开发经验,面试更重视技术栈水平。 1、重视JavaSE的基础吧,集合、泛型算是比较基础的基础,多线程、反射、JVM内存模型才是基础; 2、技术栈写到具体的点,比如Elasticsearch的使用写到某个点,限制面试官自由发挥,防止问了相关问题最后又答不上,如果真没把握建议不写,降低面试官的心理预期; 3、技术栈不要重复,比如技术栈第二条和第八条可以合并改为“熟悉Redis中间件,包括基本数据结构、缓存策略、持久化机制,了解缓存三剑客及其解决方案,并有相关项目经验。”; 4、项目指标量化,比如“达到xx秒的响应速度”(不过这个就有点偏校招社招的要求了,实习简历不写也无伤大雅)。
点赞 评论 收藏
分享
不要停下啊:大二打开牛客,你有机会开卷了,卷起来,去找课程学习,在牛客上看看大家面试笔试都需要会什么,岗位有什么需求就去学什么,努力的人就一定会有收获,这句话从来都经得起考验,像我现在大三了啥也不会,被迫强行考研,炼狱难度开局,啥也不会,找工作没希望了,考研有丝丝机会
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务