精华内容
下载资源
问答
  • 题目描述算术基本定理,又称为正整数的唯一分解定理,即:每个大于1的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。先给出一个大于1的自然数,请将其写成质因数乘积的形式,如:6=2*...

    题目大意:将一个大于1的自然数进行质因数分解,以“n=质因子乘积”的形式输出来。

    题目描述

    算术基本定理,又称为正整数的唯一分解定理,即:每个大于1的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。

    先给出一个大于1的自然数,请将其写成质因数乘积的形式,如:

    6=2*3

    12=2*2*3

    25=5*5

    37=37

    ……

    输入

    输入一个大于1的自然数

    输出

    输出质因数分解等式

    样例输入

    12345

    样例输出

    12345=3*5*823

    解题思路

    对于大于1的自然数n,其质因子从小打到可能是2、3、5、7……

    我们可以从小到大枚举因子,发现一个因子i,就除以i,除到不能整除i为止,这样n就少了一种因子了。

    如果这个因子是2,那么n除以多次2之后,后面就不会在找到4这种合数因子了。

    因此,后面继续这样找因子,找到的都是质因子,不可能是合数因子:如果有合数因子,合数可以质因数分解,说明存在更小的因子,与从小到大枚举因子相矛盾。

    最后需要注意的是,一个数的因子,一半小于等于√n,另外一半大于等于√n,为避免超时,我们只需要枚举前面小的一半;这样的话,可能会漏掉一个大的质因子,如21=3*7,i只会枚举到√21=4,7就不会枚举了;因此,如果最后n还大于1,那么剩下的n不能再分解必是一个较大的质因子。

    时间复杂度是O(√n),虽然是嵌套循环,但内重循环只会让外重循环更快介绍,循环次数并不是乘积的关系。

    程序实现

    3cdac5e0019bbe80908b824740782ef1.png

    展开全文
  • 先介绍整数的唯一分解定理: 即: 任意大于1的正整数都可以唯一分解成若干素数的乘积。 而本题的素数因子只能是2,3,5,所以抽数必定是如下形式: x=2p∗3q∗5rx = 2^p* 3^q*5^rx=2p∗3q∗5r,其中 p,q,r为非负整数p,...

    原题:https://vjudge.net/problem/UVA-136

    题目大意
    在这里插入图片描述
    题目分析

    先介绍整数的唯一分解定理:
    在这里插入图片描述
    即:
    任意大于1的正整数都可以唯一分解成若干素数的乘积。

    而本题的素数因子只能是2,3,5,所以抽数必定是如下形式:
    x = 2 p ∗ 3 q ∗ 5 r x = 2^p* 3^q*5^r x=2p3q5r,其中 p , q , r 为 非 负 整 数 p,q,r为非负整数 p,q,r

    所以,我们可以从1开始依次生成丑数,每次将生成的丑数与2,3,5因子相乘生成新的丑数,但是我们生成的丑数需要从小到大排列,所以我们使用优先队列存储生成的丑数,并且每次取出最小的丑数来继续生成。

    注意,丑数的生成方式可能并不唯一,因为一个丑数可能同时是2,3,5的倍数,所以我们需要判断生成的丑数是否重复,用setmap均可。

    /* 丑数的生成 */
    // 找出第1500个素数
    #include<iostream>
    #include<functional>
    #include<set>
    #include<queue>
    
    using namespace std;
    
    typedef long long LL;
    
    int coef[3] = { 2,3,5 }; // 3个素数因子
    set<LL> cnt; // 拿来判断该数字是否生成过
    priority_queue<LL,vector<LL>,greater<LL>> q; // 生成的数字,每次取最小的数字继续生成
    
    int main() {
    	int i;
    	LL x = 1;
    	q.push(x);
    	cnt.insert(x);
    	for (i = 1;; i++) {
    		x = q.top(); q.pop();
    		if (i == 1500) {
    			printf("The 1500'th ugly number is %ld.\n", x);
    			break;
    		}
    		for (int j = 0; j < 3; j++) {
    			LL ans = coef[j] * x;
    			if (cnt.count(ans) == 0) {
    				cnt.insert(ans); q.push(ans);
    			}
    		}
    	}
    	return 0;
    }
    
    展开全文
  • 【ACM】整数唯一分解定理

    千次阅读 2016-12-18 22:00:57
    (称为标准分解式)其中pi为素数,质数ai为正整数(如果ai=0,相当于乘一,没有意义的)。标准分解式是唯一且一定存在的。(素因子的乘积顺序不考虑)下面给出几个简单的判别式: 整数a能被2整除的充要条件是a的末尾...

    这里写图片描述
    n是大于一的任意正整数。(称为标准分解式)其中pi为素数,质数ai为正整数(如果ai=0,相当于乘一,没有意义的)。

    标准分解式是唯一且一定存在的。(素因子的乘积顺序不考虑)

    下面给出几个简单的判别式:

    1. 整数a能被2整除的充要条件是a的末尾数字为偶数。
    2. 整数a能被3整除的充要条件是a的各位数字之和能被3整除。
    3. 整数a能被5整除的充要条件是a的末尾数字为0或5 。
    4. 整数a能被11整除的充要条件是a的奇位数字之和(1.3….)和偶位数字之和(2.4…)的差的绝对值能被11整除。
    5. (很神奇)将a写成千进制数,即a=an*1000^n + an-1 *1000^n-1 + … + a1 *1000 + a0 ,其中0<=ai<1000,则a能被7(或11或13)整除的充要条件是(a0 + a2 + …) - (a1 + a3 + …) 能被7(或11或13)整除。
    #include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        int i,a[10000],c,n,t;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            c=0;
            for(i=2;i<=n;i++)
            {
                while(n%i==0)
                {
                    a[c++]=i;
                    n/=i;
                }
            }
            for(i=0;i<c;i++)
            {
                printf(i==0?"%d":"*%d",a[i]);
            }
            printf("\n");
        }
        return 0;
    }
    
    展开全文
  • 数论 —— 整数分解

    万次阅读 2018-08-01 19:32:54
    整数分解目前仍是世界级难题,是非常重要的研究方向,其有很多种算法,性能上各有差异,本文仅介绍试除法、Fermat 算法、Pollard Rho 算法。 【试除法】 试除法也叫穷举法,是整数分解算法中最简单和最容易理解的...

    【概述】

    整数分解目前仍是世界级难题,是非常重要的研究方向,其有很多种算法,性能上各有差异,本文仅介绍试除法、Fermat 算法、Pollard Rho 算法。

    【试除法】

    试除法也叫穷举法,是整数分解算法中最简单和最容易理解的算法,但也是效率最低的算法。

    试除法是用小于等于 n 的每个素数去试除待分解的整数,如果找到一个数能够整除除尽,这个数就是待分解整数的因子。

    试除法一定能够找到 n 的因子,因为它检查 n 的所有可能的因子,所以如果这个算法失败,也就证明了 n 是个素数,因此,试除法也常用来判断一个数是不是质数。

    bool judge(int n)
    {
        if(n==1)//1不是一个有效因数
            return false;
    
        for(int i=2;i<sqrt(n);i++)//如果能被整除,说明是因数
            if(n%i==0)
                retrun true;
    
        return false;
    }

    【Fermat 算法】

    Fermat 算法分解大数的效率并不高,但比起试除法要好了很多,且每次计算都是计算出 N 的一个因子,更降低了其效率。

    1.费马整数分解

    对于一个任意的偶数,我们都可以通过不断提出为 2 的质因子使其最终简化为一个 2 的 n 次幂与一个奇数,因此,任意一个奇数都可以表示为:N=2*n+1

    若这个奇数 N 是一个合数,根据唯一分解定理,其一定可以写成 N=c*d 的形式,不难发现,式中 c、d 均为奇数

    设:c>d,令 a=(c+d)/2,b=(c-d)/2

    可得:N=c*d=a*a-b*b

    例如:

    \begin{matrix}1=1*1=1^2-0^2 \\3 = 3*1 = 2^2 -1^2 \\5 = 5*1 = 3^2 - 2^2 \\ 7 = 7*1 = 4^2 - 3^2 \\ 9 = 3*3 = 3^2 - 0^2 \end{matrix}

    2.费马因式分解算法

    由于 a^2-N\geqslant b^2\geqslant 0

    因此 a^2\geqslant N

    即:a\geqslant \sqrt{c*d}=\sqrt{N}

    因此,我们可以从 a=\sqrt{N} 开始枚举,计算 a^2-N 为完全平方数即可求出 a、b,从而可以求得:c=a+b,d=a-b(a>b)

    int res[N];
    void Fermat(int n)
    {
        int a,b,temp;
    
        a=sqrt(n);
        if(a*a<n)
            a++;
        
        while(1)//y^2=x^2-n
        {
            temp=a*a-n;
            b=sqrt(a*a-n);
    
            if(b*b==temp)
                break;
            a++;
        }
        
        res[0]=a;//存储a的值
        res[1]=b;//存储b的值
    }

    【Pollard Rho 算法】

    为进一步提高效率,解决因数太多无法存储的问题,我们有了 Pollard Rho 算法。

    1.算法原理

    其原理已知待分解的大整数 n,再通过某种方法得到两个整数 a、b,计算 p=GCD(|a-b|,n),直到 p不为1,或 a、b 出现循环为止,然后再判断 p 的值,若 p=n 或 p=1,那么返回的 n 是一个质数,否则返回的 p 是 n 的一个因子,因此我们可以递归的计算 Pollard(p) 与 Pollard(n/p) ,从而求出 n 所有的因子。

    实际操作中,我们通常使用函数:x[i+1]=(x[i]*x[i]+c) mod\:n 来不断生成伪随机数,用于逐步迭代计算 a、b 的值。

    实践中,常取 c=1,再任意取两初值 a、b,即:b=a*a+1,在下一次计算中,将 b 的值赋给 a,再次使用上式来计算新的 b 的值,直至 a、b 出现循环。

    但是这样判断 a、b 的循环十分麻烦,例如生成伪随机数为:2,10,16,23,29,13,16,23,29,13...时,很难判断循环,因此我们可以采用 Floyd 判环算法来判断循环。

    2.Floyd 判环算法实现Pollard Rho 算法

    利用多项式 f(x) 迭代出 x_0,x_1,...,x_k 的值,然后设定 x、y 的初值,选用多项式进行迭代

    每次令:\left\{\begin{matrix} x=f(x) \\ y=f(f(y)) \end{matrix}\right.,即:\left\{\begin{matrix}x=x_k \\ y=x_{2k} \end{matrix}\right.

    当 x=y 时即出现循环

    int GCD(int a,int b)
    {
        return b?GCD(b,a%b):a;
    }
    
    int Pow_Mod(int a, int b, int m)
    {
        int res=1;
        while(b)
        {
            if(b&1)
                res=(res*a)%m;
            a=(a*a)%m;
            b>>=1;
        }
    }
    
    long long pollard_rho(long long x, long long c)//寻找一个因子
    {
        long long i=1,k=2;
        srand(time(NULL));
        long long x0=rand()%(x-1)+1;//产生随机数x0(并控制其范围在1 ~ x-1之间)
        long long y=x0;
        while(1)
        {
            i++;
            x0=(Pow_Mod(x0,x0,x)+c)%x;
            long long gcd=GCD(y-x0,x);
    
            if(gcd!=1&&gcd!= x)
                return gcd;
    
            if(y==x0) 
                return x;
    
            if(i==k)
            {
                y=x0;
                k+=k;
            }
        }
    }

    3.存储大整数的所有因子

    组合使用 Pollard Rho 算法与 Miller Rabin 算法,可求出大整数的所有因子。

    LL Mult_Mod(LL a,LL b,LL m)//res=(a*b)%m
    {
        a%=m;
        b%=m;
        LL res=0;
        while(b)
        {
            if(b&1)
                res=(res+a)%m;
            a=(a<<=1)%m;
            b>>=1;
        }
        return res%m;
    }
    LL Pow_Mod(LL a, LL b, LL m)//res=(a^b)%m
    {
        LL res=1;
        LL k=a;
        while(b)
        {
            if((b&1))
                res=Mult_Mod(res,k,m)%m;
    
            k=Mult_Mod(k,k,m)%m;
            b>>=1;
        }
        return res%m;
    }
    
    bool Witness(LL a,LL n,LL x,LL sum)
    {
        LL judge=Pow_Mod(a,x,n);
        if(judge==n-1||judge==1)
            return 1;
    
        while(sum--)
        {
            judge=Mult_Mod(judge,judge,n);
            if(judge==n-1)
                return 1;
        }
        return 0;
    }
    
    bool Miller_Rabin(LL n)
    {
        if(n<2)
            return 0;
        if(n==2)
            return 1;
        if((n&1)==0)
            return 0;
    
        LL x=n-1;
        LL sum=0;
        while(x%2==0)
        {
            x>>=1;
            sum++;
        }
    
    
        int times=20;
        for(LL i=1;i<=times;i++)
        {
            LL a=rand()%(n-1)+1;//取与p互质的整数a
            if(!Witness(a,n,x,sum))//费马小定理的随机数检验
                return 0;
        }
        return 1;
    }
    LL GCD(LL a,LL b)
    {
        return b==0?a:GCD(b,a%b);
    }
    LL Pollard_Rho(LL n,LL c)//寻找一个因子
    {
        LL i=1,k=2;
        LL x=rand()%n;//产生随机数x0(并控制其范围在1 ~ x-1之间)
        LL y=x;
        while(1)
        {
            i++;
            x=(Mult_Mod(x,x,n)+c)%n;
            LL gcd=GCD(y-x,n);
    
            if(gcd<0)
                gcd=-gcd;
    
            if(gcd>1&&gcd<n)
                return gcd;
    
            if(y==x)
                return n;
    
            if(i==k)
            {
                y=x;
                k<<=1;
            }
        }
    }
    
    int total;//因子的个数
    LL factor[N];//存储所有因子的数组,无序的
    void Find_fac(LL n)//对n进行素因子分解,存入factor
    {
        if(Miller_Rabin(n))//是素数就把这个素因子存起来
        {
            factor[++total]=n;
            return;
        }
    
        long long p=n;
        while(p>=n)//值变化,防止陷入死循环k
            p=Pollard_Rho(p,rand()%(n-1)+1);
    
        Find_fac(n/p);
        Find_fac(p);
    }

    【例题】 

    • Prime Test(POJ-1811)(Pollard Rho 与 Miller Rabin 求大整数分解):点击这里
    展开全文
  • 整数的唯一分解定理

    2021-08-02 17:28:50
    对于正整数n,仅存在一种方式将其分解成 n=p1^t1 * p2^t2 * ... * pk^tk 则n有(t1+1)*(t2+1)*...*(tk+1)个因子
  • 算术基本定理,又称为正整数的唯一分解定理,即:每个大于1的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。例如:   算术基本定理的内容由两部分构成: 分解的存在性; 分解的唯一...
  • 算数分解定理(唯一分解定理): 定义: 任何一个大于1的自然数 N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积 N=P1a1 P2a2P3a3…Pnan,这里P1<P2<P3…<Pn均为质数,其中指数ai是正整数。这样的分解...
  • (2)整数的唯一分解定理: 定理1(整数的唯一分解定理):任一大于1的整数都能表示成素数的乘积,即对 ∀1∈Z∀1∀1∈Z,有 a=p1p2...pn (p1≤p2≤...≤pn)(1)a=p_1p_2...p_n\,(p_1≤p_2≤...≤p_n)\qquad(1)a=p1​p2​......
  • 算术基本定理(唯一分解定理

    千次阅读 2018-08-06 16:45:30
    ...唯一分解定律:又称为正整数的唯一分解定理,即:每个大于1的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。 当题目有大数相除,求余数时,精度要求高时...
  • 前几天了解了唯一分解定理,看了之后感觉定理内容挺简单的,不知道这个定理能干什么,算是比较巧吧,这几天一下遇到了两道需要用唯一分解定理的题目。 唯一分解定理内容 两道例题 ...
  • 算术基本定理,又称为正整数的唯一分解定理,即:每个大于1的自然数均可写为几个质数的积,而且这些质因子按大小排列之后,写法仅有一种方式。 先给出一个大于1的自然数,请将其写成质因数乘积的形式,如: 6=2*3 ...
  • 唯一分解定理

    千次阅读 2019-05-18 01:00:36
    唯一分解定律:又称为正整数的唯一分解定理,即:每个大于1的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。 当题目有大数相除,求余数时,精度要求高时....就要运用唯一分解定律 ...
  • [LightOJ 1341] Aladdin and the Flying Carpet (算数基本定理(唯一分解定理)) 题目链接: https://vjudge.net/problem/LightOJ-1341 题目描述: 问有几种边长为整数的矩形面积等于a,且矩形的短边...
  • 整数的唯一分解 就是把一个数分解质因数。 朴素分解法 LL a; int p[maxn],e[maxn],num; int getZys(LL a, int *p , int *e ) { int num= 0 ; int m= sqrt (a+ 0.5 ); //所有的取根号都要...
  • 给一个正整数n,将n分解为质因数。 说明:n的质因数要么是n本身(n是素数),要么一定小于等于sqrt(n)。因此可以用小于等于sqrt(n)的数对n进行试... 1 //整数的唯一分解定理 2 int a[10000];//表示第i个质因数...
  • 不完全商与非负最小剩余 (1)分解整数: 定理1:设 a,b∈Za,b∈Za,b∈Z,其中 b>0b>0b>0,则存在唯一的 q,r∈Zq,r∈Zq,r∈Z,使得 a=bq+r (0≤r)(2)a=bq+r\,(0≤ra=bq+r(0≤r)(2)成立 (2)定义: (3)性质: 定理2:对于 a1,a2...
  • 定理:任意大于1的整数都能表示成素数的乘积,即对任一整数a > 1,有 a = p1­p­2…pn , p1­ 并且表达式是唯一的。 p[i] = k, 表示i这个质因子有k个 定义:在数论,对正整数n,欧拉函数是小于等于n的数...
  • 数论算法:唯一因子分解定理

    千次阅读 2019-09-17 19:54:25
    这里讲一下算法中常用到的唯一因子分解定理: 合数a仅能以一种方式写成如下乘积形式: a = p1^e1*p2^e2*...*pr^er 其中pi为素数,p1<p2<...<pr,且ei为正整数。例如数6000=2^4*3*5^3。 证明就不讲了,...
  • 质因数分解(唯一分解定理

    千次阅读 2017-08-21 17:42:42
    质因数分解(唯一分解定理) 基本概念: 每个合数都可以写成几个质数相乘的形式,其中每个质数都是这个合数的因数,叫做这个合数的分解质因数。 分解质因数只针对合数。 并且,每个合数能够且仅仅能够被分解为唯...
  • 准素分解定理

    2021-12-01 20:16:19
    准素分解定理 设σ是n维向量空间V上一个线性变换,p(x)是σ的最小多项式.令 p(x)=(x−λ1)r1...(x−λk)rkp(x) = (x-λ_1)^{r_1} ... (x-λ_k)^{r_k}p(x)=(x−λ1​)r1​...(x−λk​)rk​ 是p(x)在复数域Q上的...
  • 又称“自然数唯一分解定理”。任一大于1的自然数都可分解成若干质因数的连乘积,如果不计各质因数的顺序,这种分解是唯一的。 如:825=3·52·11,100=2^2*5^2。 这样的分解称为N的标准分解式。最早证明是由...
  • 浅谈唯一分解定理

    2020-06-01 10:23:56
    唯一分解定理又称算术基本定理,指:一个大于一的正整数N都可以唯一分解成有限个质数的乘积, N=p1a1 * p2a2 * p3a3 * … * pnan,这里p1< p2< p3 <…< pn均为质数,ai均为正整数.这样的式子成为N的标准...
  • 分解素因子(唯一分解定理)

    千次阅读 2019-11-22 19:29:19
    1.唯一分解定理,也叫算术基本定理,指的是任何n>=2,都可以分解为n=p1* p2 * p3 * … * pn,其中pi为质数。 其包括两个断言: 断言1:数n可以以某种方式分解成素数乘积。 断言2:仅有一种这样的因数分解。(除...
  • 算术基本定理(唯一分解定理) 一句话:   任何大于1的自然数,都可以唯一分解成有限个质数的乘积 例如对于大于1的自然数n,  这里Pii均为质数,其指数aii是正整数。  这样的分解称为的标准分解式。 唯一...
  • 任何一个正整数,都可以表示(分解)为所有素数(素数又叫质数,是因数只有两个的数)各种幂的积(1 = 任何素数 ^ 0,任何素数 = 自己 ^ 1),并且每个不同的数都只有一种分解,所以叫唯一分解定理。By the way,若...
  • 整数分解 在数学中,整数分解(英语:integer factorization)又称素因数分解(prime factorization),是将一个正整数写成几个约数的乘积。例如,给出45这个数,它可以分解成9×5。根据算术基本定理,这样的分解...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,257
精华内容 5,302
关键字:

整数分解定理