题解 | #质因数的个数#

比筛法慢，比筛法省空间

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

//分解质因数的一个关键：最多只有一个质因数是大于根号自己的 

//int是可以表示10e9的，范围没超 

void Func_eg69(void){
	int n;
	while(scanf("%d",&n) != EOF){
		if(n == 2){
			printf("1\n");
			continue;
		}
		vector<int> v;
		v.push_back(2);
		for(int i=3; i<=sqrt(n); i++){
			for(int j=0; j<v.size(); j++){
				if(v[j]>sqrt(i)){//幸存，自己是质数 
					v.push_back(i);
					break;
				}
				if(i%v[j] == 0){//寄了，是合数 
					break;
				}
			}
		}//得到了根号n以下所有质数  这个耗时应该比筛法久，但比筛法省空间
		
		int i=0;
		int cnt = 0;
		while(i<v.size()){
			while(n%v[i] == 0){
				cnt++;
				n /= v[i];
			}
			i++;
		}
		if(n==1){
			;
		}else if(n>1){//剩下了一个大于根号n的质因数。一定是个质因数，因为一个合数必可被分解质因数且大于根号n的质因数最多一个 
			cnt++;
		}
		printf("%d\n",cnt);
	}
}

int main(){
	Func_eg69();
	return 0;
}