⭐【質因子分解】約數的個數

文章目錄

• 題目描述
• 知識點
• 我的實作
• • 碼前思考
  • 代碼實作
  • 碼後反思

題目描述

知識點

質因子分解

我的實作

碼前思考

這裡需要用到《算法筆記》上一個比較偏的知識點：

代碼實作

//仍然是列印素數表的方法 
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = (int) sqrt(1e9+10);

int n; 
int input[1010];
int num=0;
int prime[maxn];
bool p[maxn]={false};

void findPrime(){
	for(int i=2;i<maxn;i++){
		if(p[i]==false){
			prime[num++]=i;
			for(int j=i+i;j<maxn;j+=i){
				p[j]=true;
			}
		}
	}
}

int main(){
	findPrime();
	while(scanf("%d",&n)!=EOF){
		for(int i=0;i<n;i++){
			scanf("%d",&input[i]);
		}
		//接下來是求解質因子時間
		for(int i=0;i<n;i++){
			int cur = input[i];
			int cnt = 1;
			int sqr = (int)sqrt(1.0*cur);
			
			for(int i=0;i<num&&prime[i]<=sqr;i++){
				int factorCnt=0;
				if(cur%prime[i]==0){
					while(cur%prime[i] == 0){
						factorCnt++;
						cur=cur/prime[i]; 
					}
				}
				cnt = cnt*(factorCnt+1);	
			}
			if(cur!=1){
				cnt = cnt*2;
			}
			printf("%d\n",cnt);
		} 
	}
	return 0;
}
           

碼後反思

加油！