分解质因数

问题描述：

求出区间[a,b]中所有整数的质因数分解。

输入格式
　　输入两个整数a，b。
输出格式
　　每行输出一个数的分解，形如k=a1*a2*a3...(a1<=a2<=a3...，k也是从小到大的)(具体可看样例)

样例输入
3 10
样例输出
3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5

提示
　　先筛出所有素数，然后再分解。
数据规模和约定
　　2<=a<=b<=10000

代码：

#include 
   
    
#include 
    
      #define max 10000 int prime[max]; int isPrime(int n) { int flag = 1; for(int i = 2; i*i <= n; i++) if(n%i == 0) flag = 0; return flag; } int getPrime(int m) { int cnt = 0; int flag = 1; for(int i = 2; i <= m; i++){ flag = 1; for(int j = 2; j*j <= i; j++) if(i%j == 0) flag = 0; if(flag) prime[cnt++] = i; } return cnt; } void split(int m) { int i = 0; int t = 0; while(m != 1){ t = m/prime[i]; if(t*prime[i] == m){ m /= prime[i]; if(m != 1) printf("%d*",prime[i]); else printf("%d",prime[i]); } else i++; } printf("\n"); } int main() { int st,end; int cnt = getPrime(10000); scanf("%d%d",&st,&end); for(int i = st; i <= end; i++) { if(isPrime(i)) printf("%d=%d\n",i,i); else { printf("%d=",i); split(i); } } return 0; }