AcWing 867. 分解质因数
算数基本定理:任何一个大于1的整数n都可以分解成若干个质因数的连乘积,如果不计各个质因数的顺序,那么这种分解是唯一的。即: x = a 1 p 1 × a 2 p 2 × a 3 p 3 × a 4 p 4 × . . . × a n p n x = a_1^{p_1}times a_2 ^{p_2}times a_3 ^{p_3}times a_4 ^{p_4}times ...times a_n^{p_n} x=a1p1×a2p2×a3p3×a4p4×...×anpn,其中 n > 1 n>1 n>1, p 1 ≤ p 2 ≤ . . . ≤ p n p_1le p_2 le ...le p_n p1≤p2≤...≤pn且都是 x x x 的质因子简易证明可以这样想,若一个数是合数,它就一定存在因子,若它的因子还是合数,那么可以继续向下分,直到无法继续分为止;若一个数是质数,那么它的因子就是1和本身。怎么分解质因子呢?可以从小到大枚举 x x x 的小因子,然后枚举到质因子时,将该质因子除干净。最后若 x > 0 x > 0 x>0 那么表示 x x x 还存在一个大质因子,就是当前的 x x x 。 代码:
时间复杂度: O ( n n ) O(nsqrt n) O(nn )
#include#include #include using namespace std; int n; void divid(int x) { for (int i = 2; i <= x / i; i ++ ) { if (x % i == 0) { int s = 0; while (x % i == 0) x /= i, s ++ ; //将质因子除干净 cout << i << " " << s << endl; } } if (x > 1) cout << x << " " << 1 << endl; //存在一个大的质因子 puts(""); } int main() { cin >> n; while (n -- ) { int x; cin >> x; divid(x); } return 0; }
参考资料:
https://www.acwing.com/activity/content/code/content/49974/
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)