频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
分解质因数
2013-11-21 09:55:11           
收藏   我要投稿
前言

之前就想写一篇关于分解质因数的文章,原因也是九度oj上有几道跟质因数分解有关的题目没有思路,这次找完工作学java的同时进行一些查缺补漏

 

 

原理&&方法

把一个合数分解为若干个质因数的乘积的形式,即求质因数的过程叫做分解质因数,分解质因数只针对合数

 

求一个数分解质因数,要从最小的质数除起,一直除到结果为质数为止。分解质因数的算式的叫短除法,和除法的性质差不多,还可以用来求多个个数的公因式:

 

以24为例:

 

2 -- 24

 

2 -- 12

 

2 -- 6

 

3 (3是质数,结束)

 

得出 24 = 2 × 2 × 2 × 3 = 2^3 * 3

 

 

代码

可先用素数筛选法,筛选出符合条件的质因数,然后for循环遍历即可,通过一道题目来show一下这部分代码

 

题目

[html]  

题目描述:  

求正整数N(N>1)的质因数的个数。  

相同的质因数需要重复计算。如120=2*2*2*3*5,共有5个质因数。  

输入:  

可能有多组测试数据,每组测试数据的输入是一个正整数N,(1<N<10^9)。  

输出:  

对于每组数据,输出N的质因数的个数。  

样例输入:  

120  

样例输出:  

5  

提示:  

注意:1不是N的质因数;若N为质数,N是N的质因数。  

 

ac代码

[cpp]  

#include <stdio.h>  

  

int main()  

{  

    int n, count, i;  

  

    while (scanf("%d", &n) != EOF) {  

        count = 0;  

  

        for (i = 2; i * i <= n; i ++) {  

            if(n % i == 0) {  

                while (n % i == 0) {  

                    count ++;  

                    n /= i;  

                }  

            }  

        }  

  

        if (n  > 1) {  

            count ++;  

        }  

  

        printf("%d\n", count);  

    }  

  

    return 0;  

}  

 

 

深入理解

我所谓的深入理解,就是通过4星的题目来灵活运用分解质因数的方法,题目如下

 

题目

[html] 

题目描述:  

给定n,a求最大的k,使n!可以被a^k整除但不能被a^(k+1)整除。  

输入:  

两个整数n(2<=n<=1000),a(2<=a<=1000)  

输出:  

一个整数.  

样例输入:  

6 10  

样例输出:  

1  

 

 

思路

a^k和n!都可能非常大,甚至超过long long int的表示范围,所以也就不能直接用取余操作判断它们之间是否存在整除关系,因此我们需要换一种思路,从分解质因数入手,假设两个数a和b:

 

a = p1^e1 * p2^e2 * ... * pn^en,  b = p1^d1 * p2^d2 * ... * pn^dn, 则b除以a可以表示为:

 

b / a = (p1^d1 * p2^d2 * ... * pn^dn) / (p1^e1 * p2^e2 * ... * pn^en)

 

若b能被a整除,则 b / a必为整数,且两个素数必护质,则我们可以得出如下规律:

若a存在质因数px,则b必也存在该质因数,且该素因数在b中对应的幂指数必不小于在a中的幂指数

 

另b = n!, a^k = p1^ke1 * p2^ke2 * ... * pn^ken,因此我们需要确定最大的非负整数k即可。要求得该k,我们只需要依次测试a中每一个素因数,确定b中该素因数是a中该素因数的幂指数的多少倍即可,所有倍数中最小的那个即为我们要求得的k

 

分析到这里,剩下的工作似乎只是对a和n!分解质因数,但是将n!计算出来再分解质因数,这样n!数值太大。考虑n!中含有素因数p的个数,即确定素因数p对应的幂指数。我们知道n!包含了从1到n区间所有整数的乘积, 这些乘积中每一个p的倍数(包括其本身)都对n!贡献至少一个p因子,且我们知道在1到n中p的倍数共有n/p个。同理,计算p^2,p^3,...即可

 

代码

[cpp] 

#include <stdio.h>  

#include <stdlib.h>  

#include <string.h>  

   

#define N 1001  

   

int prime[N], size;  

   

/**  

 * 素数筛选法进行预处理 

 */  

void initProcess()  

{  

    int i, j;  

       

    for (prime[0] = prime[1] = 0, i = 2; i < N; i ++) {  

        prime[i] = 1;  

    }  

   

    size = 0;  

   

    for (i = 2; i < N; i ++) {  

        if (prime[i]) {  

            size ++;  

            for (j = 2 * i; j < N; j += i) {  

                prime[j] = 0;  

            }  

        }  

    }  

}  

   

int main(void)  

{  

    int i, n, a, k, num, count, base, tmp, *ansbase, *ansnum;  

       

    // 预处理  

    initProcess();  

   

    while (scanf("%d %d", &n, &a) != EOF) {  

        ansbase = (int *)calloc(size, sizeof(int));  

        ansnum = (int *)calloc(size, sizeof(int));  

   

        // 将a分解质因数  

        for (i = 2, num = 0; i < N && a != 1; i ++) {  

            if (prime[i] && a % i == 0) {  

                ansbase[num] = i;  

                ansnum[num] = 0;  

                   

                while (a != 1 && a % i == 0) {  

                    ansnum[num] += 1;  

                    a = a / i;  

                }  

   

                num ++;  

            }  

        }  

   

        // 求最小的k  

        for (i = 0, k = 0x7fffffff; i < num; i ++) {  

            base = ansbase[i];  

            count = 0;  

            while (base <= n) {  

                count += n / base;  

                base *= ansbase[i];  

            }  

   

            tmp = count / ansnum[i];  

            if (tmp < k) k = tmp;  

        }  

   

        printf("%d\n", k);    

    }  

   

    return 0;  

}  

   

/************************************************************** 

    Problem: 1104 

    User: wangzhengyi 

    Language: C 

    Result: Accepted 

    Time:0 ms 

    Memory:916 kb 

****************************************************************/  

 

 

约数个数定理

对于一个大于1的正整数n可以分解质因数:n = p1^a1 * p2^a2 * p3^a3 * ... * pn^an, 则n的正约数的个数为:(a1 + 1) * (a2 + 1) * ... *(an + 1).其中p1,p2,..pn都是n的质因数,a1, a2...an是p1,p2,..pn的指数

 

证明

n可以分解质因数:n=p1^a1 * p2^a2 * p3^a3 * … * pk^ak,

 

由约数定义可知p1^a1的约数有:p1^0, p1^1, p1^2......p1^a1 ,共(a1+1)个;同理p2^a2的约数有(a2+1)个......pk^ak的约数有(ak+1)个

 

故根据乘法原理:n的约数的个数就是(a1+1)*(a2+1)*(a3+1)*…* (ak+1)

 

题目

[html] view plaincopy

题目描述:  

输入n个整数,依次输出每个数的约数的个数  

输入:  

输入的第一行为N,即数组的个数(N<=1000)  

接下来的1行包括N个整数,其中每个数的范围为(1<=Num<=1000000000)  

当N=0时输入结束。  

输出:  

可能有多组输入数据,对于每组输入数据,  

输出N行,其中每一行对应上面的一个数的约数的个数。  

样例输入:  

5  

1 3 4 6 12  

样例输出:  

1  

2  

3  

4  

6  

 

代码

[cpp]  

#include <stdio.h>  

#include <stdlib.h>  

   

#define N 40000  

   

typedef long long int lint;  

   

int prime[N], size;  

   

void init()  

{  

    int i, j;  

   

    for (prime[0] = prime[1] = 0, i = 2; i < N; i ++) {  

        prime[i] = 1;  

    }  

       

    size = 0;  

   

    for (i = 2; i < N; i ++) {  

        if (prime[i]) {  

            size ++;  

            for (j = 2 * i; j < N; j += i)  

                prime[j] = 0;  

        }  

    }  

}  

   

lint numPrime(int n)  

{  

    int i, num, *ansnum, *ansprime;  

    lint count;  

   

    ansnum = (int *)malloc(sizeof(int) * (size + 1));  

    ansprime = (int *)malloc(sizeof(int) * (size + 1));  

   

    for (i = 2, num = 0; i < N && n != 1; i ++) {  

        if (prime[i] && n % i == 0) {  

            ansprime[num] = i;  

            ansnum[num] = 0;  

            while (n != 1 && n % i == 0) {  

                ansnum[num] += 1;  

                n /= i;  

            }  

            num ++;  

        }  

    }  

   

    if (n != 1) {  

        ansprime[num] = n;  

        ansnum[num] = 1;  

        num ++;  

    }  

   

    for (i = 0, count = 1; i < num; i ++) {  

        count *= (ansnum[i] + 1);  

    }  

   

    free(ansnum);  

    free(ansprime);  

   

    return count;  

}  

   

   

int main(void)  

{  

    int i, n, *arr;  

    lint count;  

   

    init();  

   

    while (scanf("%d", &n) != EOF && n != 0) {  

        arr = (int *)malloc(sizeof(int) * n);  

        for (i = 0; i < n; i ++) {  

            scanf("%d", arr + i);  

        }  

   

        for (i = 0; i < n; i ++) {  

            count = numPrime(arr[i]);  

            printf("%lld\n", count);  

        }  

   

        free(arr);  

    }  

   

    return 0;  

}  

/************************************************************** 

    Problem: 1087 

    User: wangzhengyi 

    Language: C 

    Result: Accepted 

    Time:190 ms 

    Memory:1068 kb 

****************************************************************/  

 

 

 

 

 

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 质因数
上一篇:任务调度Quartz和spring整合
下一篇:ENet网络库教程翻译
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站