数论 |
您所在的位置：网站首页 › 素因子不超过2个的数 › 数论 |
|
质因数
1.定义 指能整除给定正整数的质数 简而言之就是一个数既要是 n n n 的因子，有要是一个质数，这样的数被称为 n n n 的一个质因数，或者被称为 n n n 的一个质因子。2.求一个数的所有质因数（分解质因数） 2.1 唯一分解定理(算术基本定理) 任何一个大于1的自然数 N {N} N ，如果 N {N} N不为质数，都可以唯一分解成有限个质数的乘积 N = P 1 α 1 ∗ P 2 α 2 ∗ ⋯ ∗ P n α n N = {P_1}^{\alpha_1}*{P_2}^{\alpha_2}* \cdots *{P_n}^{\alpha_n} N=P1α1∗P2α2∗⋯∗Pnαn ，这里 P 1 < P 2 < ⋯ < P n {P_1} < {P_2} if(n % i == 0)//如果 n % i == 0 的话，它就保证 n 中已经没有了 1 ~ i - 1 的因子，同样也保证了 i 中也没有了1 ~ i - 1 的因子 { //这样就保证了 i 一定是一个质数，同样 i 一定是 n 的一个质因子 int s = 0;//用 s 来记录指数的次数 while(n % i == 0)//把 i 除完了， n 中已经没有 i 的质因子了，对于后面含有 i 的素因子的合数，也就再也不能被 n 整除了 { //而根据唯一分解定理，每一个合数都能表示成素因子乘积的形式 //所以再筛到这个合数的之前，它的素因子必定已经被除完了，所以就不会筛到合数。 s++; n /= i; //把 n 缩小到 n / i, 就相当于再对 n / i 这个数进行质因数分解 } printf("%d %d\n", i, s);//输出质因数 i 和它的指数 s } } if(n != 1)printf("%d 1\n",n); //如果最后剩下的那个数不等于1的话，那么这个数就是那个大于sqrt(n)的那个质数，或者 n 本身就是一个质数 }通过这个方法，我们就可以在 O ( n ) O(\sqrt{n}) O(n ) 的时间内完成分解质因数。 但是我们可以观察，如果 n n n 为 2 2 2 的整数次幂时，在第一次循环的时候就可以结束，时间复杂度为 O ( l o g n ) O(logn) O(logn) ，所以试除法的时间复杂度在 O ( l o g n ) O(logn) O(logn) ~ O ( n ) O(\sqrt{n}) O(n )之间，一般来说会远小于 O ( n ) O(\sqrt{n}) O(n ) 。 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |