分解质因数

简介: 分解质因数

题目描述:

分解质因数听起来既熟悉又陌生,从小学就了解过概念并使用过,但用代码如何实现不得不思考一下。下面重温下什么是质数和合数,质数又称素数,有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。合数指自然数中除了能被1和本身整除外,还能被其他数(0除外)整除的数。



核心思想:从最小质数开始作为除数(质数满足小于被除数),寻找可以被目标数整除的质数并输出,同时保留商作为下一次运算被除数。


#include <iostream>
using namespace std;
int main ()
{
  int n,i=2;
  cin>>n;
  cout<<n<<"=";
  do {
    while(n%i==0) {
      cout<<i;
      n=n/i;
      if(n!=1) cout<<"*";
    }
    i++;
  }
  while(n!=1);
    return 0;
}
目录
打赏
0
0
0
0
1
分享
相关文章
筛质数、分解质因数和快速幂的应用
筛质数、分解质因数和快速幂的应用
94 0
|
7月前
辗转相除法
【10月更文挑战第21天】辗转相除法。
74 2
求其最大公约数和最小公倍数
求其最大公约数和最小公倍数。
141 5
辗转相除法求最大公约数
辗转相除法求最大公约数
分解质因数答疑
为什么n % i == 0就是质数 因为在枚举到i之前已经把n中2到i-1的质因子除干净了,此时n中不含2到i-1的质因子,由于n为i的倍数,所以i中也不包含2到i-1的质因子。如果i可以整除前面的i - 1中的数那么i = x * (i - 1),n = x2 * (x * (i - 1)); 矛盾了 为什么只需要枚举到根号N
132 2
辗转相除法求最大公约数(使用递归实现)~
辗转相除法求最大公约数(使用递归实现)~
110 0
汉诺塔(hanoi)问题从0到1详解
汉诺塔(hanoi)问题从0到1详解
190 0
Fibonacci数列的多种求法
Fibonacci数列的多种求法
107 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等