Transformer 海思 php kubernetes plot syntax uiview sdk vue传值 后台管理ui jquery的each循环 最新更新国内最快的dns datetimepicker赋值 java使用redis oracle创建唯一索引 python数据类型 input函数python python中set的用法 python读取mysql数据 python怎么使用 java包 javafinally java中的基本数据类型 java入门课程 java自定义异常 java环境下载 java游戏开发 计价软件 assist是什么意思 tampermonkey 联发科mt6750 掌门一对一下载 js分页 办公室复印机使用方法 华为ff 安卓adb 抠图软件免费版 抠图教程 widcomm ps二寸照片制作教程
当前位置: 首页 > 学习教程  > 编程语言

求欧拉函数(模板)

2021/2/13 20:22:32 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

互质是公约数只有1的两个整数,叫做互质整数 1.根据定义求解 比如1~6中与6互质的数只有1,5,所以6的欧拉函数是2 求一个时间复杂度:O(sqrt(n))求n个就是 n*sqrt(n&#xff…

互质是公约数只有1的两个整数,叫做互质整数

 

1.根据定义求解

 比如1~6中与6互质的数只有1,5,所以6的欧拉函数是2

 

 求一个时间复杂度:O(sqrt(n))求n个就是 n*sqrt(n)

               long res=n;
                        for(int i=2;i<=n/i;i++){
                                if(n%i==0){
                                        res=res*(i-1)/i;
                                        while(n%i==0) n/=i;
                                }
                        }
                        if(n>1) res=res*(n-1)/n;
                        System.out.println(res);

 

2.筛法求欧拉函数,时间复杂度:O(n)

       i % primes[j] == 0时:primes[j]是i的最小质因子,也是primes[j] * i的最小质因子,也就是i和i * prime[j]有相同的质因子

         

      i % primes[j] != 0:primes[j]不是i的质因子,只是primes[j] * i的最小质因子,所以多了一个质因子

      

 

 

static final int N=1000005;
        static int prime[]=new int[N];
        static boolean vis[]=new boolean[N];
        static int phi[]=new int[N];
        static int cnt,n;
        static void get_eulers(){
                phi[1]=1;//1. 1的欧拉函数为1
                for(int i=2;i<N;i++){
                        if(!vis[i]){
                                prime[cnt++]=i;
                                phi[i]=i-1;//2.质数的欧拉函数为i-1
                        }
                        for(int j=0;j<cnt&&prime[j]<N/i;j++){
                                vis[prime[j]*i]=true;
                                if(i%prime[j]==0) {
                                        phi[prime[j]*i]=phi[i]*prime[j];//3.如果prime[j]是i的最小质因子
                                        break;
                                }
                                else{
                                        phi[prime[j]*i]=phi[i]*(prime[j]-1);//4.不是最小质因子
                                }
                        }
                }
                int res=0;
                for(int i=1;i<=n;i++) res+=phi[i];
                System.out.println(res);
                
        }

 


本文链接: http://www.dtmao.cc/news_show_700457.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?