【蓝桥杯】BASIC-16 分解质因数

正文索引 [隐藏]

题目描述:

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

【提示】先筛出所有素数,然后再分解。

输入描述:

输入两个整数a,b(2<=a<=b<=10000)。

输出描述:

每行输出一个数的分解,形如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

解题思路:

开局一个TLE,水题直接运行超时把我劝退。后来发现我超时的原因是判断素数的那段代码导致的。我一开始写的isPrime函数判断素数的时候不够快。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)

//万恶的TLE 超时了
// bool isPrime(int n)    
// {
//     if(n <= 1) return false;
//     Up(i,2,sqrt(n))
//     {
//         if(n%i == 0) return false;
//     }
//     return true;
// }

int isPrime(int n)  //很神奇,以后我不要用上面的方法来判断素数啦
{
    if(n <= 1) return 0;
    else if(n==2 || n==3) 
    {
        return 1;
    }
    else
    {
        for(int i = 2; i*i < n; i++)
        {
            if(n%i == 0) return 0;
        }
        return 1;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int a,b;
    cin >> a >> b;
    Up(i,a,b)
    {
        int _ = i;
        cout << _ << "=";
        bool virgin = true;
        while(_ != 1)
        {
            Up(j,2,_)
            {
                if(isPrime(j) && _%j==0)
                {
                    _ /= j;
                    cout << (virgin?"":"*") << j;
                    virgin = false;
                    break;
                }
            }
        }
        cout << endl;
    }  
    return 0;
}