反素数

基本概念(定义 性质)

算法实现

基本概念

定义

对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数.

性质

性质一:一个反素数的质因子必然是从2开始连续的质数.

性质二:p=2^t1*3^t2*5^t3*7^t4.....必然t1>=t2>=t3>=....

算法实现

C语言实现：

#include<stdio.h>

typedef long long ll;

const int prime[16]= {1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};

ll maxsum, bestnum, n;

void getantiprime(ll num, ll k,ll sum,int limit)

{

//num：当前枚举到的数，k：枚举到的第k大的质因子；sum：该数的约数个数；limit：质因子个数上限；

int i;

ll temp;

if(sum > maxsum)

{

maxsum = sum;

bestnum = num; //如果约数个数更多，将最优解更新为当前数；

}

if(sum==maxsum && bestnum > num)

bestnum = num; //如果约数个数相同，将最优解更新为较小的数；

if(k > 15)

return;

temp = num;

for(i=1; i<=limit; i++) //开始枚举每个质因子的个数；

{

if(temp*prime[k] > n)

break;

temp = temp * prime[k]; //累乘到当前数；

getantiprime(temp, k+1, sum*(i+1), i); //继续下一步搜索；

}

}

int main(void)

{

scanf("%lld", &n);

getantiprime(1,1,1,50);

printf("%lld\", bestnum);

return 0;

}