质因数分解

　

质因数分解

算术基本定理：任何一个大于 1 的整数都能唯一分解为有限个质数的乘积。

试除法：结合质数质数判定的“试除法”和质数筛选的“Eratosthenes筛法”，我们可以枚举 2~sqrt(n) 中的每个数 d ，若 d 能整除 N，则从 N 中除掉所有的因子 d ，同时累计除去因子 d 的个数。

因为一个合数的因子一定在扫描到这个合数之前就从 N 中被除掉了，所以在上述过程中能整除 N 的一定是质数。

特别地，若 N 没有被 2~sqrt(N) 的数整除，则 N 是质数，无需分解。

时间复杂度为O(sqrt(n))。Pollard's Rho算法的时间复杂度为 O(sqrt(sqrt(n)))，但是不会0.0。

代码实现：

const int maxn=10005;
int c[maxn];
int p[maxn], m;
void pide(int n){
    m = 0;
    for(int i = 2; i <= sqrt(n); i++){
        if(n % i == 0){// i 是质数
            p[++m] = i, c[m] = 0;
            while(n % i == 0){
                n /= i, c[m]++;
            }
        }
    }
    if(n > 1){// n 是质数
        p[++m]=n, c[m] = 1;
    }
    for(int i = 1; i <= m; i++)
        printf("%d^%d\n", p[i], c[i]);
}

相关阅读

淘宝信誉等级的划分解释

很多想在淘宝建立网店的人，连基本的淘宝名词都不知道什么意思，怎么能能做好以后的网店推广呢?今天开始，淘宝开店流程的小编就作为一

Rushcrm:客户管理系统的客户细分解决方案

随着如今时代的发展，大部分企业都面临着一个较大的问题，就是如何在行业的竞争市场中占有更多的份额，但是随着市场的价格逐渐透明化，要

如何更好的去分解功能点

在日常工作中，都会接触到一个个的需求，通过需求分析。我们通过建立一套解决方案去满足需求的实现。再去细化的话，就是将这套解决方案

机器学习实战——SVD（奇异值分解）

与PCA一样的学习过程，在学习SVD时同样补习了很多的基础知识，现在已经大致知道了PCA的应用原理，SVD个人感觉相对要难一点，但主要步骤还

【C】质因数的个数

题目描述 求正整数N(N>1)的质因数的个数。相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。 输入描述: 可能有多组测