质因数分解模板

质因数分解

模板

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


int p[1000];
int num[1000];


bool isPrim(int n){
	
	int N = sqrt(n)+1;
	
	for(int i=2;i<=N;i++ ){
		if(n%i==0) return false;
		
	}
	return true;
}


int divide(int n){
	
	int m = 0;
	
	int N = sqrt(n)+1;
	for(int i=2;i<=N;i++){
		
		if(n%i ==0){
			p[m] = i;
			num[m] = 0;
			while(n%i ==0){
				num[m] ++;
				n/=i;
			}
			m++;
		}
		
		if(n == 1)
			break;
	}
	if(n > 1){
		p[m] = n;
		num[m] = 1;
		m++;
	}
	return m;
}


int main(){
	
	int a;
	scanf("%d",&a);
	int m = divide(a);
	
	for(int i=0;i<m;i++){
		
		printf("%d %d\n",p[i],num[i]);
	}
	
	
	
	
	return 0;
}