首页 > 代码库 > 素因子分解

素因子分解

使用唯一素因子分解定理进行:

 1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #define ll long long 5 const int MAX_N = 1000; 6 int f[MAX_N + 1]; // 存储素因子 7 int e[MAX_N + 1]; // 素因子的幂次 8 int prime_factors(int n){ 9     memset(f,0,sizeof f),memset(e,0,sizeof e);10     int cnt = 0; // 素因子的个数11     int m = (int)sqrt(n + 0.5);12     for(int i = 2 ; i <= m ; i++)if(n % i == 0){13         f[cnt] = i;14         while(n % i == 0) n /= i,e[cnt]++;15         cnt++;16     }17     if(n > 1) f[cnt] = n,e[cnt++] = 1;18     return cnt;19 }20 int main(){21     for(int i = 2 ; i <= 100 ; i++){22         int cnt = prime_factors(i); printf("%d:",i);23         for(int j = 0 ; j < cnt ; j++){24             printf("%d^%d",f[j],e[j]);25             if(j != cnt - 1) printf("*");26         }27         printf("\n");28     }29     return 0;30 }

 

素因子分解