当前位置:   article > 正文

算术基本定理(唯一分解定理)_唯一分解定理证明

唯一分解定理证明

转载自https://blog.csdn.net/qq_34446253/article/details/52211543
/-----------------------------------------------------------------------------------------------
唯一分解定律:又称为正整数的唯一分解定理,即:每个大于1的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。

当题目有大数相除,求余数时,精度要求高时…就要运用唯一分解定律

以下唯一分解定律证明:

转自:http://www.matrix67.com/blog/archives/495

为了真正地证明,分解质因数的方法是唯一的,我们将再次用到反证法。假设存在某些数,它们有至少两种分解方法。那么根据上文提到的“非空正整数集里存在最小的元素”,一定有一个最小的数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是质数矛盾了。这说明,我们最初的假设是错误的。

用e[]保存每一位素数的系数 如21*52则表示成e[1,0,2,0,0,0……] 因为素数是[2,3,5,7,11,13……], 2在第一位,5在第三位.

代码如下:

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int maxn = 10000 + 5;
int e[maxn];    //用e[]保存每一位素数的系数
vector<int> primes;
void GetPrime()
{
    int n[10000] = {0};
    for(int i = 2; i <= sqrt(10000 + 0.5); i++)
        if(!n[i])
            for(int j = i * i; j <= 10000; j += i)
                n[j] = 1;
    for(int i = 2; i <= 10000; i++)
        if(!n[i])
            primes.push_back(i);

}
void add_int(int n, int d)
{
    for(int i = 0; i < primes.size() && n != 1; i++)
        while(n % primes[i] == 0) {
            n /= primes[i];
            e[i] += d;
        }
}
int main()
{
    GetPrime();   //求出素数
    int n, p;
    cin >> n;
    add_int(n, 1); //乘以n;

    p = 0;
    for(int i = 0; i < primes.size(); i++)
        if(e[i]) {
            if(p)
                cout << '*';
            cout << primes[i] << '^' << e[i];
            if(!p)
                p = 1;
        }
    cout << endl;

    cin >> n;
    add_int(n, -1); //除以n;

    p = 0;
    for(int i = 0; i < primes.size(); i++)
        if(e[i]) {
            if(p)
                cout << '+';
            cout << primes[i] << '^' << e[i];
            if(!p)
                p = 1;
        }

    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/446890
推荐阅读
相关标签
  

闽ICP备14008679号