【蓝桥杯】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;
}
C++
Copy