基础练习分解质因数

资源限制

时间限制：1.0s 内存限制：512.0MB

问题描述

　　求出区间[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

注意分解质因数的方法

 1 #include<iostream>
 2 using namespace std;
 3 //author: Qiang
 4 int main(){
 5     int n1,n2;
 6     int i,j;
 7     cin>>n1>>n2;
 8     for(i=n1;i<=n2;i++){
 9         for(j=2;j<i;j++){
10             if(i%j==0)break;
11         }
12         if(j>=i){
13             cout<<i<<"="<<i<<endl;
14         }else{
15             cout<<i<<"="; 
16             int m=i;
17             for(int k=2;k<=m;k++){
18                 while(m!=k){
19                     if(m%k==0){
20                         cout<<k<<"*";
21                         m=m/k;
22                     }else break;
23                 }
24             }
25             cout<<m<<endl;
26         }
27     }
28 }

方法二：

 1 #include<iostream>
 2 using namespace std;
 3 //author: Qiang
 4 //int main(){
 5 //    int n1,n2;
 6 //    int i,j;
 7 //    cin>>n1>>n2;
 8 //    for(i=n1;i<=n2;i++){
 9 //        for(j=2;j<i;j++){
10 //            if(i%j==0)break;
11 //        }
12 //        if(j>=i){
13 //            cout<<i<<"="<<i<<endl;
14 //        }else{
15 //            cout<<i<<"="; 
16 //            int m=i;
17 //            for(int k=2;k<=m;k++){
18 //                while(m!=k){
19 //                    if(m%k==0){
20 //                        cout<<k<<"*";
21 //                        m=m/k;
22 //                    }else break;
23 //                }
24 //            }
25 //            cout<<m<<endl;
26 //        }
27 //    }
28 //} 
29 void zq(int n)
30 {
31     int a=2;
32     while(a*a<=n)
33     {
34         while(n%a==0)
35         {
36             cout<<a<<ends;
37             n=n/a;
38         }
39         a++;
40     }
41     if(n>1) cout<<n;
42 }
43 int main(){
44     int n1,n2;
45     int i,j;
46     cin>>n1>>n2;
47     for(i=n1;i<=n2;i++){
48         for(j=2;j<i;j++){
49             if(i%j==0)break;
50         }
51         if(j>=i){
52             cout<<i<<"="<<i<<endl;
53         }else{
54             zq(i);
55         }
56     }
57 }

欢迎交流学习

基础练习 分解质因数

基础练习分解质因数