约数个数和n的关系

求

其中为数 的约数的个数， 为常数。

结论发现 范围的数全部满足上述公式， 范围的数只有 个不满足上述公式。

时

时

时

时

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5;
const int times=2;
int prime[MAXN];
int num[MAXN],d[MAXN];

void get_di()
{
    num[1]=1;
    for(int i=2;i<MAXN;i++){
        if(!prime[i]){
            prime[++prime[0]]=i;
            num[i]=2;
            d[i]=1;
        }
        for(int j=1;j<=prime[0]&&i<MAXN/prime[j];j++){
            prime[i*prime[j]]=1;
            if(i%prime[j]==0){
                d[i*prime[j]]=d[i]+1;
                num[i*prime[j]]=num[i]/(d[i]+1)*(d[i]+2);
                break;
            }
            num[i*prime[j]]=num[i]*2;
            d[i*prime[j]]=1;
        }
    }
}

int main(void)
{
    for(int i=0;i<MAXN;i++) prime[i]=num[i]=d[i]=0;
    get_di();
    int cnt=0;
    for(int i=2;i<MAXN;i++){
        if(num[i]>=times*(int)(log(i)/log(2))+1){
            cnt++;
            // printf("%d %d\n", num[i],i);
        }
    }
    printf("%d\n", cnt);
}