蓝桥杯-分解质因数

简介: 分解质因数

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;
}


相关文章
|
5月前
|
前端开发 算法 Java
2019蓝桥杯大赛省赛Java大学B组 数的分解
2019蓝桥杯大赛省赛Java大学B组 数的分解
28 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-605 分解质因数
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-605 分解质因数
39 2
|
6月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-994 最大分解
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-994 最大分解
47 1
|
6月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-645 加法分解
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-645 加法分解
36 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-633 加法分解
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-633 加法分解
41 0
蓝桥杯2019年第十届JavaB组真题题目+解析+代码+答案:4.数的分解
蓝桥杯2019年第十届JavaB组真题题目+解析+代码+答案:4.数的分解
151 0
蓝桥杯2019年第十届JavaB组真题题目+解析+代码+答案:4.数的分解
|
Python
蓝桥杯第十一届国赛Python组试题C阶乘约数——唯一分解定理的应用
定义阶乘 n! = 1 × 2 × 3 × · · · × n。 请问 100! (100 的阶乘)有多少个约数。
220 0
蓝桥杯第十一届国赛Python组试题C阶乘约数——唯一分解定理的应用
|
C语言 C++
2019年第十届C/C++ B组蓝桥杯省赛真题(数的分解)
把 20192019 分解成 33 个各不相同的正整数之和,并且要求每个正整数都不包含数字 22 和 44,一共有多少种不同的分解方法? 注意交换 33 个整数的顺序被视为同一种方法,例如 1000+1001+181000+1001+18 和 1001+1000+181001+1000+18 被视为同一种。
260 0