最多约数问题
时间: 1ms 内存:64M
描述:
正整数x 的约数是能整除x 的正整数。正整数x的约数个数记为div(x)。例如,1,2,5,10 都是正整数10的约数,且div(10)=4。设a 和b是2 个正整数,a≤b,找出a 和b之间约数个数最多的数x。对于给定的2 个正整数a≤b,计算a 和b之间约数个数最多的数。
输入:
输入数据的第1行有2个正整数a和 b,a≤1000000000,b≤1000000000。
输出:
若找到的a 和b之间约数个数最多的数是x,将div(x)输出。
示例输入:
1 36
示例输出:
9
提示:
参考答案(内存最优[748]):
#include"stdio.h"
#include"math.h"
int div(int x)
{
int i,sum1,sum2=1;
for(i=2;i<=x/2;i++)
{
sum1=1;
while(x%i==0)
{
sum1++;
x=x/i;
}
sum2=sum2*sum1;
}
if(x>1)sum2=sum2*2;
return sum2;
}
int main()
{
int i,a,b,max;
while(scanf("%d %d",&a,&b)==2)
{
max=0;
for(i=a;i<=b;i++)
if(max<div(i))max=div(i);
printf("%d\n",max);
}
return 0;
}
参考答案(时间最优[24]):
#include<stdio.h>
#include<math.h>
int main()
{
int a,b,i,m,n=0;
int f(int);
scanf("%d %d",&a,&b);
for(i=a;i<=b;i++)
{
m=f(i);
if(m>n)
n=m;
}
printf("%d",n);
return 0;
}
int f(int a)
{
int y,i,s=0;
for(i=1;i<sqrt(a);i++)
{
if(a%i==0)
s++;
}
s=2*s;
y=sqrt(a)*1000;
if(y%1000==0)
s=s+1;
return s;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。