divi.cpp

正整数x 的约数是能整除x 的正整数。正整数x 的约数个数记为div(x)。例如

#include"stdio.h"
#include "fstream.h"

const int primeCount=6542;//素数量
const int UsedMaxPrime=65536;//可能用到的素数值的上限
int lowB,upB,maxLocate,maxCount;//下边界，上边界，最多约数所在数，最多约数的个数

void GenPrimes(int *primes){
  //用筛法生成素数表

  //声明与初始化
  int i,j;
  int *p,*p0;
  int ArrInt[UsedMaxPrime+1];
  p=&ArrInt[0];
  for (int iget=0;iget<UsedMaxPrime;iget++,p++) *p=1;
  //筛
  p=&ArrInt[2];
  p0=&ArrInt[0];
  for (i=2;i<=UsedMaxPrime;i++,p++){
    if (*p==1){
      j=i<<1;
      while (j<=UsedMaxPrime){
        *(p0+j)=0;
        j+=i;
      }
    }
  }
  //形成素数表
  p=&ArrInt[2];
  p0=primes;
  for (i=2;i<=UsedMaxPrime;i++,p++){
    if (*p==1){
      *p0=i;
      p0++;
    }
  }
}

void Iterative(int *primes,int curPrime,int curNum,int curCount,int low,int up){
  //递归求最多素数数
  int divLow,divUp,cur_num,calPrimeCount,curPri,count;
  int *p;
  //判断更新maxCount
  if ((curNum<up) && (curCount*2>maxCount)) {
    maxCount=curCount*2;
  }
  if ((curNum>=lowB) && (curCount>maxCount)){
    maxCount= curCount;
    maxLocate= curNum;
  }
  //对各素数进行枚举，看有否符合要求的数
  p=primes+(curPrime-1);
  for (int i=curPrime;i<=primeCount;i++,p++){
    if (*p>up){
      return;
    }
    else {
      curPri=*p;
      divLow=low-1;
      divUp=up;
      cur_num=curNum;
      count=curCount;
      calPrimeCount=1;
      while (1){
        calPrimeCount++;
        count+=curCount;
        divLow=divLow/curPri;
        divUp=divUp/curPri;
        if (divLow==divUp){
          break;
        }
        cur_num=cur_num*curPri;
        Iterative(primes,i+1,cur_num,count,divLow+1,divUp);//递归搜索下一级
      }
      int LeftPosCount=maxCount>>calPrimeCount;//求余下的素数数的最大可能值，因为最小素数是2，故以2计算
      if (curCount<LeftPosCount){
        return;//余下的素数数不够多，中断
      }
    }
  }
}

void main()
{
  //输入,a,b，作为上边界upB和下边界lowB
  ifstream fin("input.txt");
  fin>>lowB>>upB;
  fin.close();
  //求结果
  int Primes[primeCount];//声明素数表
  GenPrimes(&Primes[0]);//生成素数表
  if (lowB+upB==2) {
    maxCount= 1;//a,b均等于1的特例，返回1
  }
  else {
    maxCount= 2;//大于1的数，约数个数至少为1，作为初始值
    Iterative(&Primes[0],1, 1, 1, lowB, upB);//用递归法求最大约数的个数
  }
  //输出
  ofstream fout("output.txt");
  fout<<maxCount;
  fout.close();
}