template.cpp

整数因子的求解方法

#include <iostream>  
#include <map>     
using namespace std;      

//保存素数
int w[6600]={2,3,5,7,11,13,17,19,23,29};  //6600为2^16之内素数个数的大约的一个数；全局数组

bool isPrime(int n)
{
	for(int i=0; w[i]*w[i]<=n; ++i) //循环范围的优化：循环判断到n的平方根
		if(n % w[i]==0)				//整除数的优化：只考虑素数因子，可以参考实验五中的对称五位素数问题。
			return false;  
		return true;
}

int main()
{
	//第一步骤：求出素数表
	int n=10;  //素数元素个数n最初值10
	for(int i=31; i<(1<<16); i+=2)  // 构造29之后，2^16之内素数表，增加幅度为2
		if(isPrime(i)) 
			w[n++]=i;
		
	//循环读数
	for (int a; cin>>a;)
	{
		cout <<a<<": ";

		//第二步骤：求素因子 a(b)
		//素因子 a(b): a为素因子本身；b为素因子出现的次数
		map<int, int> ma;               // 主key存放素因子，value存放分解个数  map映射、字典、关联数组
		for(int k=0; a!=1 && k<n; )     // 分解因子,n为素数表边界  a为循环读取的数
			if(a%w[k]) k++;             // 不能除尽，逻辑条件为真，w[i]不是a的因子,则尝试素数表中下一个素数
			else  ma[w[k]]++, a/=w[k];  //  如果是因子，则a的该素数个数加1,a除去该素数
		if(a>(1<<16)) 
			ma[a]++;      // 大于2^16的素因子最多只有一个，又因为a本身也是它自己的因子
		
	
		//第三步骤：从素因子，构件因子的数目
		int sum = 0;
		for(int i=0; i<(1<<ma.size()); ++i)  //共有2^ma.size()种素因子组合情况
		{ 
	    	int t=1;  //每种因子组合的情形数
			map<int,int>::iterator it=ma.begin();  //定位到map的开始元素
			for(int j=0; j<ma.size(); ++j, ++it) 
				if(i & 1<<j)  //第j位上非0，表示it定位到map中第j的元素出现在当前组合中
					t*=it->second;                   //每种因子组合中,将各个素因子个数相乘
			sum += t;                                //每种因子组合的情形数相加
		}
		cout <<sum<<endl;	// sum即为a所有因子数						
	}			
	return 0;		
}