UC知道自然数的分解c++编程
来源：百度知道 编辑：UC知道 时间：2024/06/30 22:54:29
有一个程序，自然数的分解。
自然数的分解就是将大于1的自然数分解为素数的乘积和裴彼那契数列的和，当用户输入一个自然数后，将其分解为素数的乘积和裴彼那契数列的和。并显示出来。
主要技术问题的描述：
整数分解唯一性定理，每个大于1的正整数a可以分解成有限个素因数之积，并且不计素因数的次序，其分解是唯一的（若a有一因数b，而b又是素数，则称b为a的素因数）。将自然数n分解为素数乘积时，n的素因数肯定在2—n范围内。
1，1，2，3，5，8，13，21，34……是著名的裴彼那契数列，其特点为：
某一项=它的前两项之和。
各位大哥大姐啊，帮忙编出来吧，这可能要一定的时间，我也没多少积分，你们就当是锻炼自己嘛，真的不胜感激啊…………
最好是要具体做出来啊,,,,
自然数的分解就是将大于1的自然数分解为素数的乘积和裴彼那契数列的和，当用户输入一个自然数后，将其分解为素数的乘积和裴彼那契数列的和。并显示出来。
主要技术问题的描述：
整数分解唯一性定理，每个大于1的正整数a可以分解成有限个素因数之积，并且不计素因数的次序，其分解是唯一的（若a有一因数b，而b又是素数，则称b为a的素因数）。将自然数n分解为素数乘积时，n的素因数肯定在2—n范围内。
1，1，2，3，5，8，13，21，34……是著名的裴彼那契数列，其特点为：
某一项=它的前两项之和。
各位大哥大姐啊，帮忙编出来吧，这可能要一定的时间，我也没多少积分，你们就当是锻炼自己嘛，真的不胜感激啊…………
最好是要具体做出来啊,,,,
第一个因数分解问题思路很简单，但是写起来可能会比较烦
另外注明，因数分解大合数是个世界级难题
伪代码如下：
从小到大生成2到sqrt(n)范围内的素数表prime[]，表中元素个数为p//生成方法很多，建议自己找一下
for(i=0;i<p;i++)
{
while (n%prime[i]==0)//如果n不是素数，不可能进入此while循环
{
输出prime[i]
n/=prime[i];
}
if (n>1) 输出n//此时n本身就是个素数
}
费波纳契分解自然数n相对好写一些
从小到大生成1到n范围内的斐波那契数列F[],数列个数m
for (i=m-1;n && i>=0;i--)
if (n>=F[i])
{
输出F[i]
n-=F[i];
}