【藍橋杯】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;  }