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

• 2019 年 11 月 13 日
• 筆記

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/weixin_42449444/article/details/102984695

题目描述：

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