189 8069 5689
把一个合数分解成若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数。
我们提供的服务有：成都网站建设、网站制作、微信公众号开发、网站优化、网站认证、雅安ssl等。为成百上千企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务，是有科学管理、有技术的雅安网站制作公司
1、短除法
2、树丫法
描述 Description
给出N个数字，试求质因数最大的数字。
输入格式 InputFormat
第一行，一个整数N，表示数字个数。
接下来N行，每行一个整数A_i，表示给出的数字。
输出格式 OutputFormat
一个整数，表示质因数最大的数字。
数据范围和注释 Hint
N= 5000 , A_i= 20000
举例 38和12
38=19*2
12=2*3*3
38最大的是19
12最大的是3
所以本数据要输出38
样例输入：
4
36
38
40
42
样例输出：
38
代码：
#include
#include
int a[5010];
int zhi(int n)
{
if(n==2) return 1;
for(int i=2;i=sqrt(n);i++)
if(n%i==0) return 0;
return 1;
}
int yin(int n)
{
int c;
if(zhi(n)) return n;
for(int i=2;i if(n%i==0zhi(i)) c=i;
return c;
}
int main(int argc, char *argv[])
{
int n,i,max,l;
scanf("%d",n);
for(i=0;i scanf("%d",a[i]);
max=1;
for(i=0;i if(yin(a[i])=max){
max=yin(a[i]); l=a[i];
}
printf("%d\n",l);
return 0;
}
要求一个数的质因数,首先要明白什么是质因数.
质因数=质数+因数
即,求出的数既是一个质数,而且是该数的因数.
所以求一个数的质因数就是把这个数写成很多个质数相乘的形式
如：4 = 2 * 2 = 2^2 ,6 = 2 * 3 ,18 = 2 * 3 * 3 = 2 * 3^2
//判断num是否为质数
bool IsPrimeNumber(unsigned int num)
{
if (num == 1)
return false;
unsigned int nMaxNum = num-1;
for(int n=2; nnMaxNum; n++)
{
if ((num % n)==0)
return false;
nMaxNum = (num+n-1)/n;
}
return true;
}
//计算num的质因数个数
int CalcPrimeNumberCount(unsigned int num)
{
int nPrimeCount = 0;
unsigned int nMaxNum = num-1;
for(int n=2; n=nMaxNum; n++)
{
if ((num % n) == 0)
{
if ( IsPrimeNumber(n) )
{
nPrimeCount++;
}
nMaxNum = (num+n-1) / n;
}
}
return nPrimeCount;
}
//主程序
int main(int argc, char* argv[])
{
int num = 9699690;
int nPrimeCount = CalcPrimeNumberCount(num);
printf("数字 %d 的质因数个数为 %d 个\n", num, nPrimeCount);
return 0;
}
我的代码结构清晰，容易看明白，执行效率高，刚测试过了