d120 - 10699 - Count the factors

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定正整數的質因數個數。例如，對於數字 45 (335)，輸出應為 2，因為它只有兩個不同的質因數：3 和 5。

解題思路

此題的核心在於找出一個數字的所有質因數。程式首先使用埃拉托斯特尼篩法 (Sieve of Eratosthenes) 生成小於等於 1001000 的所有質數。然後，對於每個輸入數字，程式遍歷質數列表，檢查每個質數是否能整除該數字。如果能整除，則將質因數計數器加一。最後，輸出質因數的總數。

複雜度分析

• 時間複雜度: O(N log log N + M log N)，其中 N 是篩選的上限 (1001000)，M 是輸入數字的數量。埃拉托斯特尼篩法的時間複雜度為 O(N log log N)，而對於每個輸入數字，遍歷質數列表的時間複雜度為 O(log N) (因為質數列表的大小約為 N / log N)。
• 空間複雜度: O(N)，主要用於儲存質數列表和標記非質數的陣列。

程式碼

#include <stdio.h>
int a[1001001]={0},p[78955]={0};
int main(){
	for(int i=2;i<=1001;i++)
		for(int j=i*2;j<=1001000;j+=i)
			a[j]=1;
	for(int i=0,j=2;i<78955&&j<=1001000;j++){
		if(a[j]==0){
			p[i]=j;
			i++;
		}
	}
	int b;
	while(scanf("%d",&b)){
		if(b==0)break;
		printf("%d : ",b);
		int sum=0;
		for(int i=0;p[i]<=b;i++){
			if(b%p[i]==0)
				sum++;
		}
		printf("%d\n",sum);
	}		
}