藍橋杯---分解質因數---C++

試題 基礎練習 分解質因數

資源限制

  時間限制：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

實作代碼

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

vector<int> prime;
bool isPrime[10005];

bool Judge(int num) {
	for (int j = 2; j <= sqrt(num); j++) if (num % j == 0) return isPrime[num] = false;
	return isPrime[num] = true;
}

void GetPrime(int MaxNum) {
	for (int i = 2; i <= MaxNum; i++) 
		if(Judge(i)) prime.push_back(i);
}

void Getans(int num) {
	cout << num << "=";
	if (isPrime[num]) cout << num << endl;
	else {
		int index = 0, cnt = 0;
		while (num != 1) {
			int now = prime[index];
			while (num != 1 && num % now == 0) {
				num /= now;
				if (!cnt++) cout << now;
				else cout << "*" << now;
			}
			index++;
		}
		cout << endl;
	}
}

int main() { 
	int l, r;
	cin >> l >> r;
	GetPrime(r);
	for (int i = l; i <= r; i++) Getans(i);
	return 0;
}