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 = 1;
		map<int ,int>::iterator it;

		for(it=ma.begin(); it!=ma.end(); it++)
		{
			sum*=(1+it->second);  //利用公式(1+p1)(1+p2)(1+p3)...(1+pn)，其中p1,p2,p3,...,pn表示某一个素因子的个数
		}
		cout <<sum<<endl;	// sum即为a所有因子数						
	}			
	return 0;		
}