資源限制
時間限制：1.0s 記憶體限制：512.0MB
問題描述
求出區間[a,b]中所有整數的質因數分解，
輸入格式
輸入兩個整數a，b，
輸出格式
每行輸出一個數的分解，形如k=a1a2a3…(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
提示
先篩出所有素數，然后再分解，
資料規模和約定
2<=a<=b<=10000
解題思路：
- 首先要獲取整數N的質因數
- 然后利用回圈輸出對應N的質因數，
質因數（素因數或質因子）在數論里是指能整除給定正整數的質數，除了1以外，兩個沒有其他共同質因子的正整數稱為互質，因為1沒有質因子，1與任何正整數（包括1本身）都是互質，正整數的因數分解可將正整數表示為一連串的質因子相乘，質因子如重復可以用指數表示，根據算識訓本定理，任何正整數皆有獨一無二的質因子分解式 [1] ，只有一個質因子的正整數為質數，
每個合數都可以寫成幾個質數（也可稱為素數）相乘的形式 [2] ，這幾個質數就都叫做這個合數的質因數，如果一個質數是某個數的因數，那么就說這個質數是這個數的質因數；而這個因數一定是一個質數，
轉載于：https://baike.baidu.com/item/%E8%B4%A8%E5%9B%A0%E6%95%B0/6192269?fr=aladdin
解題方法：
我自定義了一個函式find（int n），其作用是找到傳入資料n的質因數，然后再用一個自定義函式show（int x，int y）來進行輸出，在find函式中我使用了multiset容器，
不了解容器的可以瀏覽本人上一篇文章：完美的代價，同樣使用了容器，并附上了鏈接，是對set和multiset容器的詳細講解，
從2到sqrt（n），找n的質因數，然后遞回呼叫find函式即可，輸出的話要注意的是最后一項是沒有“×”的，詳細見源代碼，
源代碼：
#include<iostream>
#include<math.h>
#include<set>//multiset包含在該頭檔案中，
using namespace std;
multiset<int>m;
void find(int n)//找傳入資料n的質因數
{
int flag = 0;//一個識別符號，如果flag=0，說明該整數的質因數為其本身，
for (int i = 2; i <= sqrt(n); i++)//從2到sqrt（n）即可，此處不做詳細解釋，
{
if (n % i == 0)
{
flag = 1;//存在非其本身的質因數，改變識別符號的值，
m.insert(i);//將該質因數存入容器，
if (n / i != i)//當不相等的時候采用遞回，
{
find(n / i);
break;//!!!，此處一定要加上，原因是例如12的質因數為2和3，不加的話，程式會把4存入容器，
}
if (n / i == i)//相等的時候，直接存入容器，
{
m.insert(i);
}
}
}
if (flag == 0)//說明除了本身沒有其他質因數，例如5，就直接把n存入容器中即可，
m.insert(n);
}
void show(int x, int y)//輸出質因數的函式
{
for (int i = x; i <= y; i++)
{
find(i);
multiset<int>::iterator p = m.begin();//此處要在find（i）后定義，不然容器是空的啊！
if (m.size() == 1)
{
cout << i << "=" << i << endl;//說明質因數就是他本身
}
else
{
cout << i << "=";
for (int j = 0; j < m.size(); j++)//此處就是輸出的問題，最后一項不能有“*”這個符號，可自行理解，應該有更好的辦法，
{
if (j < m.size() - 1)
{
cout << *p << "*";
p++;
}
if (j == m.size() - 1)
cout << *p;
}
cout << endl;
}
m.clear();//不要忘記把容器清空，一個i對應一個容器，
}
}
int main()
{
int x, y;
cin >> x >> y;
show(x, y);
}
運行結果：
評測結果：
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/252239.html
標籤：其他
上一篇：c語言遞回系列總結