最多约数问题

• 问题描述：
  正整数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之间约数个数最多的那个数及最多约数个数。

  

程序示例如下：

#include <iostream>
#include <fstream>
using namespace std;
#define max Max  
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;


    // 读文件
    ifstream infile;
    infile.open("D:/input.txt");
    cout << "从input.txt中读取数据：" << endl;
    infile >> l >> u;
    cout << "两个数分别为：" << l <<"   "<< u << endl;
    infile.close();

    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;

    // 写文件
    cout << "将结果写入output.txt:" << endl;
    ofstream outfile;
    outfile.open("D:/output.txt");
    outfile << max << endl;
    outfile << numb << endl;
    outfile.close();
    cout << "写入成功！！！" << endl;

    system("pause");
    return 0;
}

void primes()
{
    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;
}

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;
        }
    }
}

运行结果：

http://blog.sina.com.cn/s/blog_e4b2e3990102vt39.html