算法竞赛--质因子分解

1.质因数的个数

求正整数N(N>1)的质因数的个数。相同的质因数需要重复计算。如120=22235，共有5个质因数。

输入:

可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。

输出:

对于每组数据，输出N的质因数的个数。

样例输入:

120
200

样例输出:

5
5

思路：该题与pat甲1059类似，该题只需统计质因数的总个数即可

代码如下:

#include <bits/stdc++.h>
bool prime[1000100]={0};
int p[1000100]={0};
int find()		//素数表
{
	int count=0;
	for(int i=2;i<1000100;i++)
	{
		if(prime[i]==false)
		{
			p[count++]=i;
			for(int j=2*i;j<1000100;j=j+i)
				prime[j]=true;
		}
	}
	return count;
}
int main()
{
	int n,count=find();
	while(scanf("%d",&n)==1)
	{
		int sn=sqrt(n),c=0;
		for(int i=0;i<count&&p[i]<=sn;i++)
		{
			if(n%p[i]==0)
			{
				while(n%p[i]==0)
				{
					c++;
					n=n/p[i];
				}
			}
			if(n==1)
				break;	
		}
		if(n!=1)
			c++;
		printf("%d\n",c);
	}
	return 0;	
}

2.约数的个数

输入n个整数,依次输出每个数的约数的个数。

输入:输入的第一行为N，即数组的个数(N<=1000)接下来的1行包括N个整数，其中每个数的范围为(1<=Num<=1000000000)当N=0时输入结束。

输出:可能有多组输入数据，对于每组输入数据，输出N行，其中每一行对应上面的一个数的约数的个数。

样例输入:

6
1 4 6 8 10 12
0

样例输出:

1
3
4
4
4
6

代码如下:

#include <bits/stdc++.h>
int main()
{
	int n;
	while(scanf("%d",&n)==1 && n)
	{
		for(int i=0;i<n;i++)
		{
			int count=0,m;
			scanf("%d",&m);
			int sm=sqrt(m);
			for(int i=1;i<=sm;i++)
			{
				if(m%i==0)
				{
					if(i==m/i)
						count++;
					else
						count=count+2;	
				}
			}
			printf("%d\n",count);
		}
	} 
	return 0;
}

3.完数与盈数

一个数如果恰好等于它的各因子（该数本身除外）子和，如：6=3+2+1，则称其为“完数”；

若因子之和大于该数，则称其为“盈数”。求出2 到60 之间所有“完数”和“盈数”，并以如下形式输出： E: e1 e2 e3 ……(ei 为完数) G: g1 g2 g3 ……(gi 为盈数)

输入信息:

无

输出信息:

按描述要求输出（注意EG后面的冒号之后有一个空格）。

输出只有1行，即名名吃巧克力的方案数。

注意:该题的输出，E和G在同一行，E的最后一个和G之间有空格

代码如下:

#include<bits/stdc++.h>
int main()
{
	int E[60],G[60];
	int ce=0,cg=0;
	for(int i=2;i<=60;i++)	//注意小于等于60，60是最后一个盈数，否则WA0.
	{
		int si=sqrt(i);
		int sum=0;
		for(int j=1;j<=si;j++)
		{
			if(i%j==0)
			{
				if(j==1||j==i/j)
					sum=sum+j;
				else
					sum=sum+j+i/j;
			}
		}
		if(sum==i)
			E[ce++]=i;
		if(sum>i)
			G[cg++]=i;
	}
	printf("E:");
	for(int i=0;i<ce;i++)
		printf(" %d",E[i]);
	printf(" G:");
	for(int i=0;i<cg;i++)
		printf(" %d",G[i]);
	printf("\n");
	return 0;
}