请问最多约数有关问题

2012-02-14

请教最多约数问题问题描述：正整数x的约数是能整除x的正整数。正整数x 的约数个数记为div(x)。例如，1，2，5，10

请教最多约数问题
问题描述：
正整数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 之间约数个数最多的数。
数据输入：
输入数据由文件名为input.txt的文本文件提供。文件的第1 行有2 个正整数 a和 b。
结果输出:
程序运行结束时，找到a 和b之间约数个数最多的那个数及最多约数个数。

测试数据：【只给出最多约数个数, time limit: 1s】
[1, 36] 9
[1000000, 2000000] 288
[999998999, 999999999] 1024
[1, 1000000000] 1344
[999999999, 1000000000] 56
[100, 1000000000] 1344
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

方法：设正整数x的质因子分解为
x＝p1^N1 × p2^N2 ×……pi^Ni
则 div（x）＝（N1＋1）（N2＋1）……（Ni＋1）。
程序运行正确，效率也行，就是下面用红色标注的语句有些不明白，还请大侠们多指教……
Environment: MS VC6.0
#include<iostream>
using namespace std;

const long MAXP = 100000;
long prim[MAXP];
long max, numb, PCOUNT; //max存放最多约数个数，numb存放约数个数最多的数

void primes(); //用筛选法产生质数存于prim数组中
void search(long from, long tot, long num, long low, long up);
int main()
{
primes();
long l, u;
cin >> l >> u;
if ((l == 1) && (u == 1))
{
max = 1;
numb = 1;
}
else
{
max = 2;
numb = l;
search(1, 1, 1, l, u);
}
cout << max << endl << numb << endl;
return 0;
}

void primes() //执行完后: prim[]={2, 3, 5, 7, 11, 13……}
{
bool get[MAXP+1];
long i;
for (i = 2; i <= MAXP; i++)
get[i] = true;

for (i = 2; i <= MAXP; i++)
if (get[i])
{
long j = i + i;
while (j <= MAXP)
{
get[j] = false;
j += i;
}
}
long ii, j;
for (ii = 2, j = 0; ii <= MAXP; ii++)
if (get[ii]) prim[++j] = ii;
PCOUNT = j;
}

// 区间[low,up]上，tot为当前约数最多个数，num为约数个数最多的数，
//from表示现在是第几个质数。
void search(long from, long tot, long num, long low, long up)
{
if (num >= 1)
if ( (tot > max) || ((tot == max) && (num < numb)) )
{
max = tot;
numb = num;
}

if ((low == up) && (low > num)) search(from, tot*2, num*low, 1, 1);

for (long i = from; i <=PCOUNT; i++)
{
if (prim[i] > up) return;
else
{
long j = prim[i], x = low - 1, y = up, n = num, t = tot, m = 1;
while (true)
{
m++;
t += tot;
x /= j;
y /= j;
if (x == y) break;
n *= j;
search(i+1, t, n, x+1, y);
}
m = 1 << m;
if (tot < max / m) return;
}//end else
}//end for
}

[解决办法]

C/C++ code

[color=#FF0000]这个函数的作用是：已知num有tot个因子，并且原区间为[num*low,num*up],求从from个素数开始，原区间内的数可以分解到的最多的约数[/color]void search(long from, long tot, long num, long low, long up){if (num >= 1)  if ( (tot > max) || ((tot == max) && (num < numb)) )  {  max = tot;  numb = num;  }     if ((low == up) && (low > num)) search(from, tot*2, num*low, 1, 1);   [color=#FF0000]这句其实可以去掉，只是为了提高效率，当满足条件时，可以预见tot至少可以达到2倍的tot，且num*low就是这个数，这里的调用只是更新max和numb的值[/color]  for (long i = from; i <=PCOUNT; i++)  {  if (prim[i] > up) return;     else  {  long j = prim[i], x = low - 1, y = up, n = num, t = tot, m = 1;  while (true) [color=#FF0000]//区间里数的分解可以分为带j的和不带j的，这里处理带j的情况[/color]  {  m++;  t += tot;  x /= j;  y /= j;  [color=#FF0000]//这里每除一次j，表示分解出一个j来[/color]  if (x == y) break; [color=#FF0000]//说明区间[x,y]中的数没有j的倍数了[/color]  n *= j;  search(i+1, t, n, x+1, y);  [color=#FF0000]//带j的分解又可以按j的次数来分类，这里m-1为当前分解中j的次数，然后递归调用[/color]  }  m = 1 << m;  if (tot < max / m) return; [color=#FF0000]//这里处理分解不带j的，进行下一次循环前先估计一下当前的分解有没有可能达到已经求得的最优解，否则没必要继续下去[/color]  }//end else  }//end for} 
 
[解决办法]
给定一个数n ，从1 开始查找 至 n 的平方根，若 i是n 的因数，那么 n/i 也为 n 的因数
下面的函数用于统计一个正数的因数的个数

C/C++ codeint count(int n){   int i = 1;   int res = 0;   for ( ; i * i <= n; ++i)   {      if (n % i == 0)         res += 2;   }   if ((i - 1) * (i - 1) == n)      res -= 1;   return res;}

热点排行

软件架构设计

请问最多约数有关问题