整数分解(integer factorization)

我会带着你远行 2023-01-20 06:53 29阅读 0赞

## 整数分解 ##

在数学中，整数分解（英语：integer factorization）又称素因数分解（prime factorization），是将一个正整数写成几个约数的乘积。例如，给出45这个数，它可以分解成9×5。根据算术基本定理，这样的分解结果应该是独一无二的。这个问题在代数学、密码学、计算复杂性理论和量子计算机等领域中有重要意义.  
具体分解算法比较多，这里用试除法实现：

#include<iostream>
      2 #include<stdio.h>
      3 
      4 using namespace std;
      5 
      6 int main(){ 
      7 
      8 int n;
      9 int a[1000], t=0;
     10 
     11 cin >> n;
     12 int m = n;
     13 for(int i = 2;i<=n;i++){ 
     14     while(n!=i){ 
     15         if(n%i ==0){ 
     16             a[t++]=i;
     17             n /= i;
     18         }else{ 
     19             break;
     20         }
     21     }
     22 a[t] = n;
     23 }
     24 
     25 cout << m << "=";
     26 for(int i = 0;i <=t;i++){ 
     27     cout << a[i];
     28     if(i!=t){ 
     29     cout << "*";
     30     }
     31 }
     32 cout << endl;
     33 return 0;
     34 }

测试结果：  
![测试结果][20210511162249264.png_pic_center]  
[对于整数分解参考资料：][Link 1]

[20210511162249264.png_pic_center]: /images/20221021/f37a2bc0543240099d8ae806e50afad0.png
[Link 1]: https://en.wikipedia.org/wiki/Integer_factorization

发表评论取消回复

表情：

评论列表（有 0 条评论，29人围观）

还没有评论，来说两句吧...

相关阅读

相关整数质因数分解

1 问题每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。 2 方法 1. 先定义一

川长思鸟来/ 2024年03月23日 18:27/ 0 赞/ 64 阅读

相关线性代数：矩阵分解(Matrix factorization)

矩阵分解算法由奇异值分解算法（Singular Value Decomposition, SVD）演变而来，传统的奇异值分解算法只能对数据稠密的矩阵进行分解，而评分矩阵是极度稀

末蓝、/ 2023年10月05日 16:34/ 0 赞/ 31 阅读

相关整数分解(integer factorization)

整数分解在数学中，整数分解（英语：integer factorization）又称素因数分解（prime factorization），是将一个正整数写成几个约数的乘积

我会带着你远行/ 2023年01月20日 06:53/ 0 赞/ 30 阅读

相关整数因子分解

文章目录题目描述样例输入样例输出解题代码 -------------------- 题目描述整数因子分解问题。

爱被打了一巴掌/ 2022年12月28日 14:16/ 0 赞/ 211 阅读

相关 Problem 47 Distinct primes factors （分解因子）

Distinct primes factors Problem 47 The first two consecutive numbers to have two d

傷城~/ 2022年07月15日 03:22/ 0 赞/ 195 阅读

相关 1103. Integer Factorization (30)

The K-P factorization of a positive integer N is to write N as the sum of the P-th power

àì夳堔傛蜴生んèń/ 2022年05月28日 07:29/ 0 赞/ 177 阅读

相关 (PAT 1059) Prime Factors (分解质因子)

Given any positive integer N, you are supposed to find all of its prime factors, and wri

向右看齐/ 2022年03月18日 02:48/ 0 赞/ 260 阅读

相关 (PAT 1096) Consecutive Factors (质因子分解)

Among all the factors of a positive integer N, there may exist several consecutive numbe

女爷i/ 2022年03月17日 01:22/ 0 赞/ 224 阅读

相关分解机(Factorization Machines)

[分解机(Factorization Machines)推荐算法原理][Factorization Machines] 转载于:https://www.cnblogs.c

Bertha 。/ 2021年12月11日 07:09/ 0 赞/ 333 阅读

相关 1103 Integer Factorization (30 分) dfs 剪枝

The K−P factorization of a positive integer N is to write N as the sum of the P-th power

忘是亡心i/ 2021年11月02日 00:48/ 0 赞/ 297 阅读