Problem Description:
求出区间[a,b]中所有整数的质因数分解。
Input:
输入两个整数a,b。(2< =a< =b< =10000)
Output:
每行输出一个数的分解,形如k=a1*a2*a3...(a1< =a2< =a3...,k也是从小到大的)(具体可看样例)
Sample Input:
3 10
Sample Output:
3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5
解题思路:
我们可以先筛选出小于这个数本身的素数,然后再分解成它们的乘积。
程序代码:
#include<stdio.h> #include<string.h> #include<math.h> int prime(int x) { int i; if(x<2) return 0; for(i=2;i<sqrt(x);i++) { if(x%i==0) return 0; } return 1; } int main() { int a,b,i,j,t,flag=0; scanf("%d %d",&a,&b); for(i=a;i<=b;i++) { t=i; flag=0; printf("%d=",i); while(t!=1) { for(j=2;j<=t;j++) { if(t%j==0&&prime(j)) { t/=j; if(flag) printf("*"); printf("%d",j); flag=1; break; } } } printf("\n"); } return 0; }