【質因子分解】NOI 21:最大質因子序列

21:最大質因子序列     點選打開連結

總時間限制: 1000ms 記憶體限制: 65536kB

任意輸入兩個正整數m, n (1 < m < n <= 5000)，依次輸出m到n之間每個數的最大質因子（包括m和n；如果某個數本身是質數，則輸出這個數自身）。

一行，包含兩個正整數m和n，其間以單個空格間隔。

一行，每個整數的最大質因子，以逗号間隔。

5 10      

5,3,7,2,3,5      

元培-From Whf

題型/思路

     簡單質因子求解的應用。

#include <iostream>
#include<cstring>
using namespace std;
const int nmax=5000+10;
int a[nmax];//存放每個數的質因數序列
int b[nmax];//存放m~n這些數的最大質因數的序列 

int cal(int n){
	int len=0;
	for(int i=2;i<=n;i++){
		if(n%i==0){
			len++;
			a[len]=i;
		}
		while(n%i==0){
			n=n/i;
		}
	}
	//傳回最大的質因數
	return a[len];
}
int main(int argc, char** argv) {
	int m,n;
	cin>>m>>n;
	memset(a,0,sizeof(a));
	for(int i=0;i<n-m;i++){
		b[i]=cal(i+m);
		cout<<b[i]<<",";
	}
	cout<<cal(n)<<endl;
	return 0;
}