intellij idea下载 程序设计 Scala 分布式 状态模式 金融信贷 云计算架构 csv jdbc struct dynamic linktosql routing nosql angular ui router jQuery Mobile Draggabilly vue官方下载 vue代码规范 vue请求 手机banner常用尺寸 android逆向工程师 json转object kubernetes入门 python字典类型 python在线教程 python文件操作 java编程 java正则 java接口类 java编译环境 java初级入门教程 java匿名对象 java实现多线程 java框架学习 java中的map java线程停止 linuxgrep 方正流行体 asp建站系统
当前位置: 首页 > 学习教程  > 编程语言

寒假每日一题打卡day34—— AcWing 449. 质因数分解

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

【题目描述】 AcWing 449. 质因数分解 【思路】 枚举 扩展欧几里得定理 最小那个数a的范围是:[2, 根号 n], 那么最大那个数b就是 n /a import java.util.Scanner; class Main{//判断a、b是否为互为质因子public static boolean gcd(int a, int b){if…

【题目描述】
在这里插入图片描述

AcWing 449. 质因数分解

【思路】
枚举 扩展欧几里得定理
最小那个数a的范围是:[2, 根号 n], 那么最大那个数b就是 n /a

import java.util.Scanner;
class Main{
    //判断a、b是否为互为质因子
    public static boolean gcd(int a, int b){
        if(b == 0 ) return a ==1 ;
        return gcd(b, a % b);
    }
    public static void main(String args[]){
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt();
        int ans = 0;
        //最小那个数的范围是:[2, 根号 n]
        for(int a = 2; a * a <= n; a++){
            if( n % a != 0) continue;//a不是n的质因子
            int b = n / a; 
            if( gcd(a,b) ){//a、b互为质因子
                ans = b;
                break;
            }
        }
        System.out.println(ans);
        
    }
}

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

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?