python打反素数_反素数求解+反素数打表

问题描述:

对于任何正整数x,起约数的个数记做g(x).例如g(1)=1,g(6)=4.

如果某个正整数x满足:对于任意i(0

现在给一个N,求出不超过N的最大的反素数.

比如:输入1000 输出 840

思维过程:

求[1..N]中约数在大的反素数-->求约数最多的数

如果求约数的个数 756=2^2*3^3*7^1

(2+1)*(3+1)*(1+1)=24

基于上述结论,给出算法:按照质因数大小递增顺序搜索每一个质因子,枚举每一个质因子

为了剪枝:

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

因为最多只需要10个素数构造:2,3,5,7,11,13,17,19,23,29

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

反素数求解函数：

#include

#include

#define ll long long

using namespace std;

const int inf = 999999999;

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

int n;

ll bnum,bsum;

//当前枚举到的数；枚举到的第K大的质因子；该数的约数个数；质因子个数上限。

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

{

//如果