素数因子分解

原创

给定某个正整数 N,求其素因子分解结果,即给出其因式分解表达式 N=p​1​​​k​1​​​​⋅p​2​​​k​2​​​​⋯p​m​​​k​m​​​​。
输入格式:
输入long int范围内的正整数 N。
输出格式:
按给定格式输出N的素因式分解表达式,即 N=p1k1*p2k2pm^km,其中pi为素因子并要求由小到大输出,指数ki为pi的个数;当ki为1即因子pi只有一个时不输出ki。
输入样例:
1323
输出样例:
1323=33*72

猛地一看像是(深搜+剪枝 处理因式分解)。仔细一想并不是。

首先,我看到题的时候第一反应是这个输出有问题,如果按照输出要求,素因子分解不唯一怎么办?

你看,还是知识点有盲区吧,数学基础踏实了,根本不会有这种问题。数学上有正整数的唯一分解定理,即:每个大于1的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。

这个定理是用反证法证明的。

假设存在某些数,它们有至少两种分解方法。那么根据上文提到的“非空正整数集里存在最小的元素”,一定有一个最小的数M,它能用至少两种方法表示成质数的乘积:
M = P1 * P2 * … * Pr = Q1 * Q2 * … * Qs
下面我们将看到,这种假设会推出一个多么荒谬的结果来。不妨设P1 <= P2 <= … <= Pr, Q1 <= Q2 <= … <= Qs。显然,P1是不等于Q1的,不然两边同时约掉它,我们就得到一个更小的有两种分解方法的数。不妨设P1 < Q1,那么我们用P1替换掉等式最右边中的Q1,得到一个比M更小的数T = P1 * Q2 * Q3 * … * Qs。令M’ = M – T,我们得到M’的两种表达:
M’ = (P1 * P2 * … * Pr) – (P1 * Q2 * … * Qs) = P1 * (P2 * .. * Pr – Q2 * … * Qs) …… (1)
M’ = (Q1 * Q2 * … * Qs) – (P1 * Q2 * … * Qs) = (Q1 – P1) * Q2 * … * Qs ……………… (2)
由于T比M小,因此M’是正整数。从(1)式中我们立即看到,P1是M’的一个质因子。注意到M’比M小,因此它的质因数分解方式应该是唯一的,可知P1也应该出现在表达式(2)中。既然P1比所有的Q都要小,因此它不可能恰好是(2)式中的某个Q,于是只可能被包含在因子(Q1-P1)里。但这就意味着,(Q1-P1)/P1除得尽,也就是说Q1/P1-1是一个整数,这样Q1/P1也必须得是整数。我们立即看出,P1必须也是Q1的一个因子,这与Q1是质数矛盾了。这说明,我们最初的假设是错误的。

反正就是求出一个等式来保证了程序的完备性。

在解决这个问题之前请思考:输出格式。因为是它肯定给出了算法要求。

按给定格式输出N的素因式分解表达式,即 N=p1k1*p2k2pm^km,其中pi为素因子并要求由小到大输出,指数ki为pi的个数;当ki为1即因子pi只有一个时不输出ki。

输出格式首先是个等式并且肯定有等式满足。

其实吧,这就是个数学问题,数学好的这个题水到渠成。

1,等式怎样满足,请思考。

2,如何尽可能少的在long int范围内判断素数,请思考。

3,表达式底数从小到大排序,如何实现,请思考。

4,指数如何实现,请思考。

对于第一个问题。

满足等式可以用整除(即余数为0)判断解决。

对于第二个问题,很有必要在第一问整除除数必须要是素数。所以用数组记录数是否是素数是需要的,故埃氏筛选法首选。

对于第三个问题

for循环,用vector记录,数组也行。

对于第四个问题,到这儿你会发现,第四个问题好难解决。不要慌,你能发现可以利用第三问,如果可以整除就把数记录,那么如果记录的数如果一样那么指数++;遍历也往后推移。

OK,上代码

#include<iostream>

#include<string>

#include<cmath>

#include<vector>

using namespace std;

int main()

{

    vector<int>P;

    int A[10000]={0};

    int i,j;

    for(i=2;i<10000;i++)

    {

        if(A[i])

        {

            for(j=i*i;j<10000;j+=i)

            {

                A[j]=1;

            }

        }

    }//艾氏筛选法筛选素数

    long n;

    cin>>n;

    cout<<n<<"=";

    while(1)

    {

    long t=n;

    for(int k=2;k<=sqrt(n);k++)

    {

        if(A[k]==0&&n%k==0)

    {

        P.push_back(k);

        n/=k;

        break;

    }

    }

    //记录可整除素数数组

    if(n==t)

    {

        P.push_back(n);

        break;

    }

    }

//当然特例,该数本身就是素数,能整除的只有其本身。

    int sum=1;

    for(int q=0;q<P.size()-1;q++)

    {

        if(P[q]==P[q+1])

        {

            sum++;

        }

        //如果出现指数形式,不输出q往后移。同时记录指数,如果不相等,就可以把状态输出。

        else{

            if(sum==1)

                cout<<P[q]<<"*";

                //一个的时候不用出现“^”符号。

            else{

                cout<<P[q]<<"^"<<sum<<"*";

                    sum=1;

                    //不止一个的时候输出"^",并且输出后状态初始。

            }

        }

    }

    //sum为指数

    //最后一个后面没有符号,当然得特殊处理。

    if(sum==1)

        cout<<P[P.size()-1];

    else

        cout<<P[P.size()-1]<<"^"<<sum;

    return 0;

}


over,只要数学好,啥题都能做。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 定点小数运算 来自:http://www.eepw.com.cn/article/17893.htm 在DSP世界...
    郝宇峰阅读 9,345评论 0 2
  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,415评论 0 2
  • 时间过好快 明天要去复查 不知道怎么样 今天和安徽郜西夫妇一起安静的吃了烤鱼 去玩了特别弱智的密室逃脱 去开心的唱...
    只是找一个地方码子_阅读 233评论 0 0
  • 修养的大半年里,许久不出门。周末的时候,我收到许多来自校友的邀请,都说我在大山里边不出门了。在大学舍友的盛情邀...
    雨后逢初夏阅读 405评论 0 1
  • 那年冬日的某一天,我和我的两位姐姐做了两个多小时的车程去了殡仪馆,到达殡仪馆时已经接近中午,破旧的殡仪馆散发着一种...
    落辰云阅读 419评论 0 0