素因子分解(递归求解)

简介: 素因子分解(递归求解)

描述:


给定某个正整数 N,求其素因子分解结果,即给出其因式分解表达式


N = p1k1 * p2k2… pmkm


输入:

输入long int范围内的正整数N。

输出:

pi由小到大输出,当ki==1时可以直接输出pi。


思路:

一个典型的递归求解问题,注意特判输入的数为‘1’即可;


#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ll maxx = 1e18;
const int N = 1e6+100;
const int p = 1e4;
const double eps = 1e-8;
ll k;
ll judge(ll n)
{
  if(n<2) return 0;
  for(ll i=2;i<=n/i;i++)
    if(n%i==0)
      return 0;
    return 1;
}//判断素数 
void Prime(ll n)
{
  if(n==1) return ;//递归函数跳出条件,分解到 1 就结束 
  int cnt=0;
  for(int i=2;;i++)
  {
    if(n%i==0&&judge(i)==1)//是素因数 
    {
      cout<<i;//输出这个数 
      while(n%i==0)
      {
        cnt++;
        n/=i;
      }//找相同的数的个数 
      //相同的数个数直接用一个while循环来找,没必要再调用递归 
      if(cnt==1)
      {
        if(n!=1)
          cout<<"*";
      }//没有相同的输出乘号,注意判断这个数不是最后一个数 
      else
      {
        if(n==1)
          cout<<"^"<<cnt;
        else
          cout<<"^"<<cnt<<"*";
      }//有相同的输出幂次和乘号,注意判断是不是最后一个 
      break;
    }
  }
  Prime(n);//再次调用 
}
int main()
{
  cin>>k;
  cout<<k<<"=";
  if(k==1)//特判 1 
  {
    cout<<k;
    return 0;
  }
  else
    Prime(k);//调用函数 
  return 0; 
}


反思:


相同的数个数直接用一个while循环来找,没必要再调用递归,节省时间


目录
相关文章
|
Web App开发 前端开发 JavaScript
27 个前端动画库让你的交互更加炫酷
很多时候我们在开发前端页面时都会做一些动画效果来提升用户体验度和页面美观度,所以今天就来给大家推荐几个好用的JavaScript动画库,希望对各位小伙伴有所帮助!
2927 0
|
网络协议 应用服务中间件 网络安全
|
分布式计算 大数据 Hadoop
大数据||zookeeper来实现HDFS自动故障转移
namenode启动都是standby。 利用zookeeper来选举一个为active ZooKeeper客户端ZKFC: ZKFailoverController 给namenode添加失效备缓监控器(ZKFC: ZKFailoverCon...
1752 0
|
5月前
|
人工智能 自然语言处理 搜索推荐
AI智能导诊系统开发技术解析
智能导诊系统基于人工智能、大数据和医疗信息化技术,优化患者就医流程,提升资源匹配效率。其核心功能包括智能分诊、症状自评与风险评估及就医路径规划,通过自然语言处理、医学知识图谱、多模态交互等技术实现精准服务。系统可将门诊误挂率从23%降至6%,并显著提高急危重症识别效率,为患者提供全流程导航支持。
314 3
|
JavaScript API 开发者
vue自定义Hooks函数使用和封装思想
【8月更文挑战第8天】vue自定义Hooks函数使用和封装思想
435 1
|
7月前
|
人工智能 自然语言处理 测试技术
Potpie.ai:比Copilot更狠!这个AI直接接管项目代码,自动Debug+测试+开发全搞定
Potpie.ai 是一个基于 AI 技术的开源平台,能够为代码库创建定制化的工程代理,自动化代码分析、测试和开发任务。
588 19
Potpie.ai:比Copilot更狠!这个AI直接接管项目代码,自动Debug+测试+开发全搞定
|
9月前
|
负载均衡 监控 安全
HTTP代理IP的安全与稳定技术与策略的结合
随着科技与互联网的发展,企业对代理的需求日益增长。为加强HTTP代理IP的安全性和稳定性,可采取用户教育、使用加密协议、定期更换IP、监控可用性、设置访问控制、负载均衡、配置防火墙及定期更新维护等措施。这些方法能有效提升代理服务的安全性和可靠性。
198 7
|
11月前
|
JavaScript 前端开发 索引
JavaScript ES6及后续版本:新增的常用特性与亮点解析
JavaScript ES6及后续版本:新增的常用特性与亮点解析
380 4
|
11月前
|
设计模式 缓存 前端开发
React中样式解决方案有哪些?
本文首发于微信公众号“前端徐徐”,探讨了React开发中的样式管理方法,包括内联样式、常规CSS、CSS-Module、CSS-in-JS及使用CSS框架等五种常见方案,分析了各自的优缺点,帮助开发者根据项目需求选择合适的样式解决方案。
286 0
|
JSON Java fastjson
JSON与Java的两种解析方式
JSON与Java的两种解析方式