UVa 10699

題目

http://domen111.github.io/UVa-Easy-Viewer/?10699

多筆輸入，每筆輸入包含一個正整數 $X$ ， 求 $X$ 有多少不同的質因數

想法

先透過質數篩找到每個數的最小質因數 $p$ ，再透過不斷的除以 $p$ 直到剩下 $1$ 為止，中間除去重複的以外，剩下就是答案

Code

//By Koios1143
#include<iostream>
const int MaxN = 1e6+5;
int fact[MaxN];
using namespace std;
int n,cnt,p;
int main(){
	for(long long i=2 ; i<=MaxN ; i++){
		if(!fact[i]){
			fact[i]=i;
			for(long long j=i*i ; j<=MaxN ; j+=i){
				if(!fact[j]){
					fact[j]=i;
				}
			}
		}
	}
	while(cin>>n && n){
		cnt=0;
		cout<<n<<" : ";
		while(n!=1){
			p=fact[n];
			cnt++;
			while(n%p==0){
				n/=p;
			}
		}
		cout<<cnt<<"\n";
	}
	return 0;
}

複雜度分析

質數篩的複雜度為 $O(NloglogN)$

每筆測資質因數分解時間複雜度約為 $O(\Omega(X))$ 也有人說是約為 $O(logX)$

總時間複雜度約為 $O(NloglogN + \Omega(X))$