因数分解与算数基本定理

引理1：令p是素数，假设p整除乘积ab，则p整除a或b（或p既整除a也整除b）。
定理1： 假设素数p整除乘积a1a2···ar, 则p整除a1，a2，···，ar,中至少一个因素。
定理2（算数基本定理）：每个整数n≥2可唯一分解成素数乘积
n=p1p2···pr

例如：12=2·2·3与12=3·2·2看成相同的因式分解。
练习： 编写将（正）整数n分解成素数乘积的程序。（如果n=0,确保转到出错信息而不是出现死循环）。表示n的因式分解的简便方法是2×r阶矩阵，因此，如果n=p1k1p2k2 ···prkr,
则将n的因式分解存储成矩阵

（如果你的计算机不允许动态存储分配，则必须确定存储多少因素的预存量）
（1）编写程序，通过试除每一个可能因数d=2,3,4,5,6, ···分解n。
（2）修改程序存储前100个素数，在找大因素前先将n除去这些素数，如果你不管2或3或5倍数的d，而只把较大的d作为可能的因数，那么可提高程序运行速度，利用m不能被2与 之间任何数整除时，m必为素数的事实，也可提高效率，用你的程序求1000000与1000030间所有整数的完全因式分解。

#include using namespace std;int main()
{int m,n;cin>>n>>m;for(int j=n; j<=m; j++){int a=j;for(int i=2; i<a; i++){while(a!=i){if(a%i==0){cout<<i<<" * ";a=a/i;}elsebreak;}}cout << a << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！